[C] Un piccolo aiuto sulla complessità computazionale

[P_1_6]

Il mio primo algoritmo funzionante per la decodifica di un RSA=p*q
dove RSA,p,q sono nella forma 6h+1 (in realtà fattorizza anche Rsa=6h+5 ma non è proprio sempre efficiente ma è facilmente ampliabile) e tenendo conto che in un RSA di solito p/q<2.

volevo chiedervi qual'è la complessità computazionale ?

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int fattorizza_RSA_sei_h_1_sei_h_1(int *cicli,int RSA);

int main(){
    int RSA=0;

    int cicli=0;
    int jolly;

    int fattore=1;

    scanf("%d",&RSA);
    printf("\n%d\n",RSA);
    jolly=(sqrt(RSA/2))/6;

        fattore=fattorizza_RSA_sei_h_1_sei_h_1(&cicli,RSA);
    printf("\n%d è diviso da %d in %d cicli\n",RSA,fattore, cicli);
}


fattorizza_RSA_sei_h_1_sei_h_1(int *cicli,int RSA){
        int jolly=(sqrt(RSA/2))/6;
        int i=0;
        int G=(RSA-1)/6;
        int A=(G-jolly)/(6*jolly+1);
        int B=(G-A)/(6*A+1);
        int C=2;
            while((6*B+1)*(RSA/(6*B+1))!=RSA && (C*(RSA/C)!=RSA && C!=1)){
                B++;
                (*cicli)++;
                C=(-6*i+sqrt(36*i*i+4*RSA))/2;
                i++;
            }
        if(C*(RSA/C)==RSA){return C;}
        return (6*B+1);
}

[P_1_6]

Provo a dare una mezza soluzione:
Se $RSA=p*q$ e $p=6a+1$ e $q=6b+1$ allora
una parte dell'algoritmo avrà la complessità $b-a$ questa $C=(-6*i+sqrt(36*i*i+4*RSA))/2;$
l'altra parte $b-(((RSA)/(sqrt((RSA)/2)/6)-1)/6)$

Però non capisco quando si incrociano cioè qual'è la complessità del algoritmo con input $RSA=p*q$ dove $2>q/p>1$

[P_1_6]

Per renderlo più efficiente

sostituire

"P_1_6":

int jolly=(sqrt(RSA/2))/6;

con

int jolly=(sqrt(2*RSA))/6;

[P_1_6]

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
/*rossella è ottimizzato per fattorizzare numeri RSA =p * q dove RSA,p e q sono nella forma 6*h+1*/
/*Autore Alberico Lepore*/



int rossella(long long int *cicli,long long int RSA);

int main(){
    long long int RSA=0;

    long long int cicli=0;
    long long int jolly;

    long long int fattore=1;

    scanf("%lli",&RSA);
    printf("\n%lli\n",RSA);
    jolly=(sqrt(RSA/2))/6;

        fattore=rossella(&cicli,RSA);
    printf("\n%lli è diviso da %lli in %lli cicli\n",RSA,fattore, cicli);
}


rossella(long long int *cicli,long long int RSA){

        long long int jolly[99];
        int j=0;
        long long int i=0;
        long long int G=(RSA-1)/6;
        long long int A[99];
        long long int B[99];
        long long int C=2;
        long long int D[99];
        long long int maggiore=0;
        long long int E=0;

        for(j=0;j<100;j++){
            jolly[j]=(j+1);

        }

        for(j=0;j<100;j++){
            A[j]=(G-jolly[j])/(6*jolly[j]+1);
            B[j]=(G-A[j])/(6*A[j]+1);

        }

        j=0;
        while(j<100){
            while(A[j]>B[j]){
                D[j]=B[j];
                A[j]=(G-6*B[j]-1)/(6*(6*B[j]+1));
                B[j]=(G-A[j])/(6*A[j]+1);
                (*cicli)++;
            }
            j++;
        }



        for (j=0;j<100;j++){
            if(D[j] > maggiore){
                maggiore=D[j];

            }
        }

        E=(G-maggiore)/(6*maggiore+1);

        if(E>((sqrt(RSA))-1)/6){
            while((RSA/(6*E+1))*(6*E+1)!=RSA){
                E--;
                (*cicli)++;
            }
        }else{
            for(j=7;j<=sqrt(RSA);j++){
                    printf("\nj=%d\n",j);
                if(RSA%j==0){
                    printf("\nl'algoritmo rossella è ottimizzata per RSA reali anche se implementato con long long int\n");
                    return j;
                }
            }
        }
            return (6*E+1);

}

[P_1_6]

while(j<100){
            while(A[j]>B[j]){
                D[j]=B[j];
                A[j]=(G-6*B[j]-1)/(6*(6*B[j]+1));
                B[j]=(G-A[j])/(6*A[j]+1);
                (*cicli)++;
            }
            j++;
        }

Per piacere mi potreste dire come evitare il ciclo interno.
Cioè come posso sapere in un colpo solo quando A diventa minore di B?

[P_1_6]

ULTIMA VERSIONE

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
/*rossella è ottimizzato per fattorizzare numeri RSA =p * q dove RSA,p e q sono nella forma 6*h+1*/
/*Autore Alberico Lepore*/

int rossella(long long int *cicli,long long int RSA);

int main(){
    long long int RSA=0;

    long long int cicli=0;
    long long int jolly;

    long long int fattore=1;

    scanf("%lli",&RSA);
    printf("\n%lli\n",RSA);
    jolly=(sqrt(RSA/2))/6;

        fattore=rossella(&cicli,RSA);
    printf("\n%lli è diviso da %lli in %lli cicli\n",RSA,fattore, cicli);
}

rossella(long long int *cicli,long long int RSA){

        long long int jolly[99];
        int j=0;
        long long int i=0;
        long long int G=(RSA-1)/6;
        long long int A[99];
        long long int B[99];
        long long int C=2;
        long long int D[99];
        long long int maggiore=0;
        long long int E=0;

        for(j=0;j<100;j++){
            jolly[j]=(j+1);

        }

        for(j=0;j<100;j++){
            A[j]=(G-jolly[j])/(6*jolly[j]+1);
            B[j]=(G-A[j])/(6*A[j]+1);

        }

        j=0;
        while(j<100){
            while(A[j]>B[j]){
                D[j]=B[j];
                A[j]=(G-6*B[j]-1)/(6*(6*B[j]+1));
                B[j]=(G-A[j])/(6*A[j]+1);
                (*cicli)++;
            }
            j++;
        }

        for (j=0;j<100;j++){
            if(D[j] > maggiore){
                maggiore=D[j];

            }
        }


        E=maggiore;

        if(E<((sqrt(RSA))-1)/6){
            while((RSA/(6*E+1))*(6*E+1)!=RSA){
                E--;
                (*cicli)++;
            }
        }else{
            for(j=7;j<=sqrt(RSA);j++){
                    printf("\nj=%d\n",j);
                if(RSA%j==0){
                    printf("\nl'algoritmo rossella è ottimizzata per RSA reali anche se implementato con long long int\n");
                    return j;
                }
            }
        }
            return (6*E+1);

}

[P_1_6]

un altro test di fattorizzazione
http://www.albericolepore.org/al-test-d ... di-lepore/