Algoritmi sui numeri primi.

[P_1_6]

Ciao ho scritto un pseudo-codice per decodificare RSA
Per ora ho scritto solo RSA=X*Y dove X e Y e RSA sono nella forma 6Z+1
C'è qualche volontario per il test
http://www.albericolepore.org/lepore-factorization-rsa/

[P_1_6]

Ho provato di nuovo http://www.albericolepore.org/2-fattori ... di-lepore/

Hey Zoff e gli altri, voglio dirvi una cosa almeno quì c'è libertà.
Mi hanno bannato addirittura dal gruppo https://www.facebook.com/groups/perognix/

[DragonLife]

Ho provato di nuovo http://www.albericolepore.org/2-fattori ... di-lepore/

Hey Zoff e gli altri, voglio dirvi una cosa almeno quì c'è libertà.
Mi hanno bannato addirittura dal gruppo https://www.facebook.com/groups/perognix/

Perché ti hanno rimosso?

[P_1_6]

hanno rimosso il post
poi ho chiesto spiegazioni
purtroppo senza risposte

[P_1_6]

3rd Lepore primality test and factorization in O (log n)
http://www.albericolepore.org/3rd-lepor ... n-o-log-n/
Cerco feedback grazie

[crx]

Quella pagina che indichi non esiste, ma questa sì:
http://www.albericolepore.org/2nd-lepor ... ecode-rsa/

Questo è al mio livello, per cui mi ci sono messo e ne ho ricavato un programmino. Il codice l'ho buttato giù in qualche ritaglio di tempo, quindi spero di non aver fatto errori:

Codice: Seleziona tutto

program project1;
uses
  sysutils;

var
  PDM, RSA, A, B, C, ALFA, BETA, GAMMA, DELTA: Integer;
  e, f: Integer;
  i, j, k: Integer;
  MaxIter: Integer;
  AN : array [1..2] of Real;
  cN : array [1..2] of Integer = (1, 2);
  exit: Boolean;

  Res: String;

begin
  Write('RSA: ');
  ReadLn(RSA);
  Write('Numero massimo di iterazioni: ');
  ReadLn(MaxIter);
  WriteLn();

  PDM := round((sqrt(RSA)-1) / 6);

  j := 0;
  exit := False;

  ALFA := -6;
  if (RSA mod 6 = 1) then begin
    {
    (b+a)-2*PDM=j -> b = j + 2*PDM - a
    (6a+1)(6b+1)=RSA / (6a+5)(6b+5)=RSA -> (6a+c)(6b+c)=RSA ->
    -> 6ab + 6ac + 6bc + c^2 = RSA

    -> 6*a*(j + 2*PDM - a) + 6ac + 6(j + 2*PDM - a)c + c^2 = RSA
    6aj + 12aPDM - 6a^2 + 6ac + 6jc + 12cPDM - 6ac + c^2 = RSA
    -6a^2 + a(6j + 12PDM) + (6jc + 12cPDM + c^2 - RSA) = 0

    ALFA = -6
    BETA = 6j + 12PDM
    GAMMA = 6jc + 12cPDM + c^2 - RSA

    a = (-BETA +/- sqrt(BETA^2 - 4 ALFA GAMMA)) / 2 ALFA

    con c = 1, 5
        j = variabile
        PDM = int((sqrt(RSA)-1)/6)
    }
    repeat
      for i := 1 to 2 do begin
          BETA := 6 * j + 12 * PDM;
          GAMMA := 6 * j * cN[i] + 12 * cN[i] * PDM + cN[i] * cN[i] - RSA;
          DELTA := BETA*BETA-4*ALFA*GAMMA;
          if DELTA >= 0 then begin
            AN[1] := (-BETA + sqrt(DELTA))/(2*ALFA);
            AN[2] := (-BETA - sqrt(DELTA))/(2*ALFA);
            for k := 1 to 2 do begin
                if frac(RSA/(6*AN[k]+1))=0 then begin
                  A := round(AN[k]);
                  exit := True;
                end;
            end;
          end;
      end;
      Inc(j);
      if j > MaxIter then begin
        exit := True;
      end;
    until exit;
  end
  else if (RSA mod 6 = 5) then begin
    {
    (b+a)-2*PdM= j -> b = j + 2*PdM - a
    (6a+1)(6b+5)=RSA or (6a+5)(6b+1)=RSA -> (6a+e)(6b+f)=RSA (con e,f = 5,1)

    6ab + 6af + 6be + fe - RSA = 0
    6a(j + 2*PdM - a) + 6af + 6(j + 2*PdM - a)e + fe - RSA = 0
    6aj + 12aPDM - 6a^2 + 6af + 6ej + 12PDM - 6ae + fe - RSA = 0
    -6a^2 + a(6j + 12PDM + 6f - 6e) + (6ej + 12PDM + fe - RSA) = 0

    ALFA = -6
    BETA = 6j + 12PDM + 6f - 6e
    GAMMA = 6ej + 12PDM + fe - RSA
    }
    repeat
      for i := 1 to 2 do begin
          // Prima prova
          e := 5;
          f := 1;

          BETA := 6 * j + 12 * PDM + 6 * (f - e);
          GAMMA := 6 * e * j + 12 * PDM + f * e - RSA;
          DELTA := BETA*BETA-4*ALFA*GAMMA;
          if DELTA >= 0 then begin
            AN[1] := (-BETA + sqrt(DELTA))/(2*ALFA);
            AN[2] := (-BETA - sqrt(DELTA))/(2*ALFA);
            for k := 1 to 2 do begin
                if frac(RSA/(6*AN[k]+1))=0 then begin
                  A := round(AN[k]);
                  exit := True;
                end;
            end;
          end;

          // Seconda prova
          e := 1;
          f := 5;

          BETA := 6 * j + 12 * PDM + 6 * (f - e);
          GAMMA := 6 * e * j + 12 * PDM + f * e - RSA;
          DELTA := BETA*BETA-4*ALFA*GAMMA;
          if DELTA >= 0 then begin
            AN[1] := (-BETA + sqrt(DELTA))/(2*ALFA);
            AN[2] := (-BETA - sqrt(DELTA))/(2*ALFA);
            for k := 1 to 2 do begin
                if frac(RSA/(6*AN[k]+1))=0 then begin
                  A := round(AN[k]);
                  exit := True;
                end;
            end;
          end;
      end;
      Inc(j);
      if j > MaxIter then begin
        exit := True;
      end;
    until exit;
  end
  else begin
    WriteLn('RSA non divisibile');
  end;

  WriteLn();

  B := 6*A+1;
  C := RSA div B;

  Res := Format('X x Y = %d x %d = %d', [B, C, B*C]);

  WriteLn('Iterazioni: ', j);
  WriteLn(Res);

end.

Purtroppo non si può allegare un eseguibile, se lo vuoi compilare devi usare fpc (oppure te lo invio tramite mail).

Risultato: se quello che ho scritto rispetta il tuo algoritmo, non funziona.
Ad esempio, in questo caso torna:

Codice: Seleziona tutto

RSA: 35
X x Y = 7 x 5 = 35

Ma basta cambiare valori e...

Codice: Seleziona tutto

RSA: 143
X x Y = 1 x 143 = 143

Codice: Seleziona tutto

RSA: 55 
X x Y = 55 x 1 = 55

Il risultato non è sbagliato, anche se un po' inutile...

[P_1_6]

grazie ho apportato
in rosso le modifiche

[crx]

Scusami ma così hai aggiunto una nuova equazione: il sistema diventa di tre equazioni e due incognite...

[P_1_6]

di programmazione non ne capisco
dobbiamo trovare un protocollo spero che anche per te le formule vadano bene.

[crx]

Non è questione di programmazione, ma di matematica da secondo anno di superiori: tre equazioni in due incognite significa che se va bene la terza equazione è inutile, se va male è sbagliato il sistema.
Poi non si può andare per tentativi e sperare: si trova prima un ragionamento che porti da qualche parte, e poi si applica (ed eventualmente si raffina progressivamente).

PS: io non credo di avere le capacità di risolvere quel problema (soprattutto in O(log n)), ma mi aveva incuriosito provare il tuo algoritmo. L'uovo di colombo potrebbe esistere, ma prima di dire "Fatto!" dovresti almeno provare a vedere se funziona.

[P_1_6]

Poi non si può andare per tentativi e sperare: si trova prima un ragionamento che porti da qualche parte, e poi si applica (ed eventualmente si raffina progressivamente).

scusami ma purtroppo ho il vizietto di dare alcune cose per scontate e soprattutto di frammentare le informazioni.
guarda qui http://www.albericolepore.org/2-fattori ... di-lepore/ la modifica che ho fatto si poteva osservare
*************************************************************************************************************

PS: io non credo di avere le capacità di risolvere quel problema (soprattutto in O(log n)), ma mi aveva incuriosito provare il tuo algoritmo. L'uovo di colombo potrebbe esistere, ma prima di dire "Fatto!" dovresti almeno provare a vedere se funziona.

scommetto che se guardi http://www.albericolepore.org/lepore-factorization-rsa/
troverai molte relazioni interessanti altro che O(log n)
te ne mostro una
per il numero 15770980399=115981*135979
{{3504662311+2a^2+a-{[2628496733-(6a^2+2a)]/(6a+1)-2}*(6a+1)}}/[2628496733-(6a^2+2a)]=10
*********************************************************************************************************

P.S. questa {52696224+2a^2+a-{{[15808867-(6a^2+2a)]/(6a+1)-14}*(6a+1)}}/[15808867-(6a^2+2a)]=[15808867-(6a^2+2a)]
per il numero 9511*9973=94853203

[crx]

Ehm... Ma cosa significano quei numeri?
Boh. Forse sei un novello Ramanujan, ma io non capisco molto di quello che dici...

[P_1_6]

Ehm... Ma cosa significano quei numeri?
Boh. Forse sei un novello Ramanujan, ma io non capisco molto di quello che dici...

per il numero 15770980399=115981*135979
{{3504662311+2a^2+a-{[2628496733-(6a^2+2a)]/(6a+1)-2}*(6a+1)}}/[2628496733-(6a^2+2a)]=10
significa che [B+2a^2+a-(n-2)X]/nX=10
questo pezzo B+2a^2+a lo capisci da qua http://www.albericolepore.org/lepore-factorization-rsa/
nX lo capisci da qua http://www.albericolepore.org/2-fattori ... di-lepore/

[P_1_6]

vi allego due sorgenti in C per la fattorizzazione di un numero RSA=p*q ove RSA,p e q sono nella forma 6h+1 ma si può generalizzare a tutti i numeri e 1< q/p<2 ma li ho scritti in modo tale che fattorizzino per qualsiasi q/p.

Al si basa sapendo che G=(RSA-1)/6 e che se p=6a+1 e q=6b+1 allora si ha (G-a)/(6a+1)=b e quindi (G-b)/(6b+1)=a quindi si G=6ab+b+a quindi [G-(a+b)]/6=ab

invece Al_rossella

rossella trova il range

Al lo sfrutta e fattorizza

Speranzoso in una Vostra risposta cordialmente Vi saluto.

Codice: Seleziona tutto

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
long long int al(long long int RSA,long long *cicli);

int main(){
long long int RSA=1;
long long int fattore=1;
long long int cicli=0;

printf("Inserisci il primo numero\n");
    scanf("%lli",&RSA);
    clock_t start = clock();
    fattore=al(RSA,&cicli);
    clock_t end = clock();
    printf("Tempo di esecuzione =  %f secondi \n", ((double)(end - start)) / CLOCKS_PER_SEC);
    printf("\n%lli e' diviso da %lli calcolato in %lli cicli\n",RSA,fattore,cicli);
}


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

    long long int minimo_somma=2*(sqrt(RSA)-1)/6;
    long long int a=1;
    long long int G=(RSA-1)/6;
    long long int resto=G%6;
    long long int prodotto;
    minimo_somma=minimo_somma - (minimo_somma%6);


    while((6*a+1)*(RSA/(6*a+1))!=RSA || 6*a+1==1){
        prodotto=(G-(minimo_somma+resto))/6;
        a=(minimo_somma+resto + sqrt((minimo_somma+resto)*(minimo_somma+resto)-4*prodotto))/2;
        minimo_somma=minimo_somma+6;
        (*cicli)++;
    }

return (6*a+1);
}

Codice: Seleziona tutto

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
/*Al + rossella è un algoritmo di fattorizzazione generico ottimizzato serve per fattorizzare numeri NR =p * q dove NR,p e q sono nella forma 6*h+1*/
/*Autore Alberico Lepore*/

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


int main(){
long long int RSA=1;
long long int fattore=1;
long long int cicli=0;

printf("Inserisci il primo numero\n");
    scanf("%lli",&RSA);
    clock_t start = clock();
    fattore=Al(RSA,&cicli);
    clock_t end = clock();
    printf("Tempo di esecuzione =  %f secondi \n", ((double)(end - start)) / CLOCKS_PER_SEC);
    printf("\n%lli e' diviso da %lli calcolato in %lli cicli\n",RSA,fattore,cicli);

}


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

    long long int minimo_somma=rossella(cicli,RSA);
    long long int a=1;
    long long int G=(RSA-1)/6;
    long long int resto=G%6;
    long long int prodotto;
    long long int i=1;
    long long int y=2;
    minimo_somma=(minimo_somma + (RSA/minimo_somma)-1)/6;
    minimo_somma=minimo_somma - (minimo_somma%6);


    while((6*a+1)*(RSA/(6*a+1))!=RSA || 6*a+1==1){
        prodotto=(G-(minimo_somma+resto))/6;
        a=(minimo_somma+resto + sqrt((minimo_somma+resto)*(minimo_somma+resto)-4*prodotto))/2;
        minimo_somma=minimo_somma+6;
        (*cicli)++;
        y=RSA/(6*i+1);
        if((6*i+1)*y==RSA){
            break;
        }
        i++;
    }
    if((6*i+1)*(RSA/(6*i+1))==RSA){
        return (6*i+1);
    }
    return (6*a+1);
}


long long 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)+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];

            }
        }



            return (6*maggiore+1);

}

[ubuntumate]

Lui cracca tutto e Rivest è un babbeo perché qui c'è Lo Hacker https://it.m.wikipedia.org/wiki/Loacker ... oacker.jpg

[P_1_6]

ho installato ubuntu ed ho usato gcc ed ho trovato l'errore del vettore.

[P_1_6]

In più si può osservare che:
(6h+1)*(6k+1)=6G+1
(6h+5)*(6k+5)=6G+1
(6h+1)*(6k+5)=6G+5
(6h+5)*(6k+1)=6G+5

nel secondo caso basta moltiplicare per 25 il numero da fattorizzare
nel terzo e quarto caso per 5

P.s.
Qualche volontario per scrivere le funzione in base 6 di grandi numeri:
addizione
sottrazione
moltiplicazione
divisione
radice quadrata
modulo 6
minore o maggiore
uguale

[rpadovani]

In più si può osservare che:
(6h+1)*(6k+1)=6G+1
(6h+5)*(6k+5)=6G+1
(6h+1)*(6k+5)=6G+5
(6h+5)*(6k+1)=6G+5

Quindi,

(6h+1)*(6k+1) = (6h+5)*(6k+5)
36hk + 6k + 6k + 1 = 36hk +30h + 30k + 25
-24h = 24k + 24
h = -k -1

Ma anche
(6h+1)*(6k+5) = (6h+5)*(6k+1)
36hk + 30h + 6k + 5 = 36hk +6h + 30k + 5
24h = 24k
h = k


Da cui h = k = -1/2.

Però, sono scoperte importanti.

[P_1_6]

che complessità ha Al_rossella?

[P_1_6]

In questo momento inizio la fattorizzazione di 188198812920607963838697239461650439807163563379417382700763356422988859715234665485319060606504743045317388011303396716199692321205734031879550656996221305168759307650257059
che è il primo della lista http://isiloniq.com/emc-plus/rsa-labs/h ... umbers.htm

Si brucerà prima il computer oppure lo fattorizzerò?