Algoritmi sui numeri primi.

[P_1_6]

se può essere di aiuto ho notato che se N=P*Q con Pe Q numeri di Mersenne l'algoritmo è velocissimo
Esempio:

N = 658416274830184544125027519921443515789888264156074733099244040126213682497714032798116399288176502462829255784525977722903018714434309698108208388664768262754316426220651576623731617882923164117579624827261244506084274371250277849351631679441171018418018498039996472549893150577189302871520311715179730714312181456245097848491669795997289830612988058523968384808822828370900198489249243399165125219244753790779764466236965135793576516193213175061401667388622228362042717054014679032953441034021506856017081062617572351195418505899388715709795992029559042119783423597324707100694064675909238717573058764118893225111602703838080618565401139902143069901117174204252871948846864436771808616432457102844534843857198735242005309073939051433790946726672234643259349535186268571629077937597838801337973092285608744209951533199868228040004432132597073390363357892379997655878857696334892216345070227646749851381208554044940444182864026513709449823489593439017366358869648168238735087593808344484365136284219725233811605331815007424582890821887260682886632543613109252862114326372077785369292570900594814481097443781269562647303671428895764224084402259605109600363098950091998891375812839523613295667253813978434879172781217285652895469194181218343078754501694746598738215243769747956572555989594598180639098344891175879455994652382137038240166358066403475457
P= 1475979915214180235084898622737381736312066145333169775147771216478570297878078949377407337049389289382748507531496480477281264838760259191814463365330269540496961201113430156902396093989090226259326935025281409614983499388222831448598601834318536230923772641390209490231836446899608210795482963763094236630945410832793769905399982457186322944729636418890623372171723742105636440368218459649632948538696905872650486914434637457507280441823676813517852099348660847172579408422316678097670224011990280170474894487426924742108823536808485072502240519452587542875349976558572670229633962575212637477897785501552646522609988869914013540483809865681250419497686697771007
a=2
b=4
c=3

real 1m9.237s
user 1m9.228s
sys 0m0.001s

[LUBO-BACK]

Yafu con 340 numeri, senza plugin e col mio processore va ovviamente in crash

All'inizio dà div: ovvero prova a dividere per i numeri piccoli

poi fmt: prova con Fermat

dopo rho: cerca fattori piccoli con algoritmi statistici

Poi si arrende fac: job type determined to be gnfs

ma io non ho scaricato la parte di codice per fare il General Number Field Sieve (cioè il gnfs) perciò tutto fallisce

Ecco il log. yafu funziona molto bene fino a che riesce ad evitare la forza bruta.


lucab@luca-surfacego2:~/yafu$ ./yafu "3646154850295011369707131011438711095400799139943170490872585628683549034362552065955809589514611470241298944167703929337528884908857116141935206466329731087514964112054543019336536216107629523597606330154669196064144182472739556974502462402438903115845725630946428943768540714098264727068026730424033578827886916761701429264950573899186177"


fac: factoring 3646154850295011369707131011438711095400799139943170490872585628683549034362552065955809589514611470241298944167703929337528884908857116141935206466329731087514964112054543019336536216107629523597606330154669196064144182472739556974502462402438903115845725630946428943768540714098264727068026730424033578827886916761701429264950573899186177
fac: using pretesting plan: normal
fac: no tune info: using qs/gnfs crossover of 95 digits
fac: no tune info: using qs/snfs crossover of 95 digits
div: primes less than 10000
fmt: 1000000 iterations
rho: x^2 + 3, starting 1000 iterations on C340
rho: x^2 + 2, starting 1000 iterations on C340
rho: x^2 + 1, starting 1000 iterations on C340
nfs: searching for brent special forms...
nfs: searching for homogeneous cunningham special forms...
nfs: searching for XYYXF special forms...
nfs: searching for direct special forms...
nfs: snfs form detection took 0.094893 seconds
nfs: couldn't find special form
fac: job type determined to be gnfs
ecm: ECM executable does not exist at ../ecm-install/bin/ecm
ecm: no linked internal ECM, ECM may be disabled
ecm: 34/34 curves on C340, B1=2k, B2=gmp-ecm default
ecm: ECM executable does not exist at ../ecm-install/bin/ecm
ecm: no linked internal ECM, ECM may be disabled
ecm: 86/86 curves on C340, B1=11k, B2=gmp-ecm default
ecm: ECM executable does not exist at ../ecm-install/bin/ecm
ecm: no linked internal ECM, ECM may be disabled
ecm: 214/214 curves on C340, B1=50k, B2=gmp-ecm default, ETA: 0 sec
ecm: ECM executable does not exist at ../ecm-install/bin/ecm
ecm: no linked internal ECM, ECM may be disabled
ecm: 430/430 curves on C340, B1=250k, B2=gmp-ecm default, ETA: 0 sec
ecm: ECM executable does not exist at ../ecm-install/bin/ecm
ecm: no linked internal ECM, ECM may be disabled
ecm: 910/910 curves on C340, B1=1M, B2=gmp-ecm default, ETA: 0 sec
ecm: ECM executable does not exist at ../ecm-install/bin/ecm
ecm: no linked internal ECM, ECM may be disabled
ecm: 2351/2351 curves on C340, B1=3M, B2=gmp-ecm default, ETA: 0 sec
ecm: ECM executable does not exist at ../ecm-install/bin/ecm
ecm: no linked internal ECM, ECM may be disabled
ecm: 4482/4482 curves on C340, B1=11M, B2=gmp-ecm default, ETA: 0 sec
ecm: ECM executable does not exist at ../ecm-install/bin/ecm
ecm: no linked internal ECM, ECM may be disabled
ecm: 7557/7557 curves on C340, B1=43M, B2=gmp-ecm default, ETA: 0 sec
ecm: ECM executable does not exist at ../ecm-install/bin/ecm
ecm: no linked internal ECM, ECM may be disabled
ecm: 17884/17884 curves on C340, B1=110M, B2=gmp-ecm default, ETA: 0 sec
ecm: ECM executable does not exist at ../ecm-install/bin/ecm
ecm: no linked internal ECM, ECM may be disabled
ecm: 42057/42057 curves on C340, B1=260M, B2=gmp-ecm default, ETA: 0 sec
ecm: ECM executable does not exist at ../ecm-install/bin/ecm
ecm: no linked internal ECM, ECM may be disabled
ecm: 55958/55958 curves on C340, B1=850M, B2=gmp-ecm default, ETA: 0 sec
nfs: gnfs parameters table has 66 rows spanning 91-185 digits
nfs: snfs parameters table has 23 rows spanning 75-185 digits
nfs: commencing nfs on c340: 3646154850295011369707131011438711095400799139943170490872585628683549034362552065955809589514611470241298944167703929337528884908857116141935206466329731087514964112054543019336536216107629523597606330154669196064144182472739556974502462402438903115845725630946428943768540714098264727068026730424033578827886916761701429264950573899186177
nfs: searching for brent special forms...
nfs: searching for homogeneous cunningham special forms...
nfs: searching for XYYXF special forms...
nfs: searching for direct special forms...
nfs: snfs form detection took 0.098919 seconds
nfs: couldn't find special form
nfs: thread 0 commencing polynomial search over range: 2048 - 2298
error: stage 1 bound not provided
lucab@luca-surfacego2:~/yafu$

[P_1_6]

Grazie

[Actarus5]

Premesso che per me la sezione corretta sarebbe programmazione, comunque, potresti provare con questo numero:

1000000000000128000000000003367

[P_1_6]

Premesso che per me la sezione corretta sarebbe programmazione, comunque, potresti provare con questo numero:

1000000000000128000000000003367

ho provato per 10 min e non va.
tu sai il perchè su alcuni numeri è veloce e su altri no ?

[Actarus5]

Premesso che per me la sezione corretta sarebbe programmazione, comunque, potresti provare con questo numero:

1000000000000128000000000003367

ho provato per 10 min e non va.
tu sai il perchè su alcuni numeri è veloce e su altri no ?

Sì, prendi ad esempio questo:

Codice: Seleziona tutto

time ./a.out 

N = 1125897758834689

P= 2147483647

a=2

b=1

c=10


real    0m0,007s

user    0m0,003s

sys    0m0,003s 

Qua essendo P=2^(31)-1 ( numero di Mersenne), l'ordine moltiplicativo d della base a=2 è molto piccolo e vale ovviamente 31.
Deve vale la condizione (b * Q)^c ≡ 1 (mod 31)
Con questo numero vale c=10 per soddisfare la condizione e siccome nel tuo ciclo while hai come condizione c <= 20 va tutto bene.
Succede sempre coi numeri di Mersenne perché sono sempre numeri del tipo 2^qualcosa - 1 e siccome nel codice la base a parte da 2, l'ordine moltiplicativo diventa esattamente quel piccolo esponente, nell'esempio scelto 31.
Ciò implica che l'esponente c che vuoi calcolare sarà un divisore di 31 - 1 = 30. In questo ovviamente 10 divide perfettamente 30, ed infatti trovi subito c=10.


Col numero che ti ho dato io credo che c sia qualcosa come un milione e passa...

[P_1_6]

Premesso che per me la sezione corretta sarebbe programmazione, comunque, potresti provare con questo numero:

1000000000000128000000000003367

ho provato per 10 min e non va.
tu sai il perchè su alcuni numeri è veloce e su altri no ?

Sì, prendi ad esempio questo:

Codice: Seleziona tutto

time ./a.out 

N = 1125897758834689

P= 2147483647

a=2

b=1

c=10


real    0m0,007s

user    0m0,003s

sys    0m0,003s 

Qua essendo P=2^(31)-1 ( numero di Mersenne), l'ordine moltiplicativo d della base a=2 è molto piccolo e vale ovviamente 31.
Deve vale la condizione (b * Q)^c ≡ 1 (mod 31)
Con questo numero vale c=10 per soddisfare la condizione e siccome nel tuo ciclo while hai come condizione c <= 20 va tutto bene.
Succede sempre coi numeri di Mersenne perché sono sempre numeri del tipo 2^qualcosa - 1 e siccome nel codice la base a parte da 2, l'ordine moltiplicativo diventa esattamente quel piccolo esponente, nell'esempio scelto 31.
Ciò implica che l'esponente c che vuoi calcolare sarà un divisore di 31 - 1 = 30. In questo ovviamente 10 divide perfettamente 30, ed infatti trovi subito c=10.


Col numero che ti ho dato io credo che c sia qualcosa come un milione e passa...

grazie

mi piacerebbe aver un ulteriore chiarimento:

In generale dato un generico N (il numero da fattorizzare)
e
MCD[(a^((b*N)^c-1)-1) mod (N) , N]=P
dove cercare con più efficacia a,b,c ?

[Actarus5]

grazie

mi piacerebbe aver un ulteriore chiarimento:

In generale dato un generico N (il numero da fattorizzare)
e
MCD[(a^((b*N)^c-1)-1) mod (N) , N]=P
dove cercare con più efficacia a,b,c ?

Figurati, purtroppo il vero problema è come calcolare c, per il teorema di Eulero che credo tu conosca c è uno dei divisori della funzione φ. Per un N a caso potrebbe essere un numero nell'ordine di 10^9 o peggio...

Non è per scoraggiarti, però non si può fare di meglio... Pure l'algoritmo p-1 di Pollard presenta i suoi limiti se N non è "smooth"

[P_1_6]

grazie

mi piacerebbe aver un ulteriore chiarimento:

In generale dato un generico N (il numero da fattorizzare)
e
MCD[(a^((b*N)^c-1)-1) mod (N) , N]=P
dove cercare con più efficacia a,b,c ?

Figurati, purtroppo il vero problema è come calcolare c, per il teorema di Eulero che credo tu conosca c è uno dei divisori della funzione φ. Per un N a caso potrebbe essere un numero nell'ordine di 10^9 o peggio...

Non è per scoraggiarti, però non si può fare di meglio... Pure l'algoritmo p-1 di Pollard presenta i suoi limiti se N non è "smooth"

ancora grazie.

ci sono altre famiglie oltre ai Mersenne dove l'ordine moltiplicativo è piccolo ?

[Actarus5]

Occhio e croce ti direi che vale per i numeri di Fermat perché la base è 2, della forma 2^(2n)+1, suppongo che in generale valga per i numeri della forma a^(n)+-1 dove a è un intero positivo non nullo, con l'accortezza di cambiare a opportunamente nel codice

[P_1_6]

Occhio e croce ti direi che vale per i numeri di Fermat perché la base è 2, della forma 2^(2n)+1, suppongo che in generale valga per i numeri della forma a^(n)+-1 dove a è un intero positivo non nullo, con l'accortezza di cambiare a opportunamente nel codice

Riguardo i numeri di Fermat

Se un primo p divide un numero di Fermat

l'ordine di p con a=2 è uguale a 2^(n+1)

quindi "piccolo" rispetto al numero di fermat ?

potrebbe essere un buon algoritmo per fattorizzare un numero di Fermat ?

[P_1_6]

Occhio e croce ti direi che vale per i numeri di Fermat perché la base è 2, della forma 2^(2n)+1, suppongo che in generale valga per i numeri della forma a^(n)+-1 dove a è un intero positivo non nullo, con l'accortezza di cambiare a opportunamente nel codice

Riguardo i numeri di Fermat

Se un primo p divide un numero di Fermat

l'ordine di p con a=2 è uguale a 2^(n+1)

quindi "piccolo" rispetto al numero di fermat ?

potrebbe essere un buon algoritmo per fattorizzare un numero di Fermat ?

Non funziona poichè tutti i fattori di fermat hanno stesso ordine