Algoritmi sui numeri primi.

[P_1_6]

reiterando e ricordandosi di scrivere m in funzione di a e b e testando per m=0 e b=5 ed m=2 e b=7
solve m=0 , b=5 , [[sqrt(117-n*a)+1]/2]^2-(m/2)^2=[a*b- (2 +2*(b-1))*(b-1)/2] , b=[sqrt(117-n*a)+1]/2-m/2 , a=sqrt(117-n*a) , a^2+n*a=117

[P_1_6]

Hey admin
mi fate sapere qualcosa anche se la risposta è negativa.
Ho fatto dei calcoli teorici ed un numero di 100 cifre viene fattorizzato in poco più di 300 step
E' tutto vero datemi un opportunità.
Ciao.

[P_1_6]

ormai l'ho pubblicato solo che sbagliavo è in O([log_9(N)]^3)
https://www.academia.edu/35412746/Test_ ... _log_9_N_3_

[P_1_6]

Hey amici potreste dare uno sguardo?
Che ne pensate?

EDIT
Testing m, r, s, t, v, z,

n-m=1
m-r=1
r-s=1
s-t=1
t-v=1
v-z=1
etc.etc.

[P_1_6]

ragazzi qualcuno che lo implementi c'è?
E' in O(log_2())

Dai @Zoff

[P_1_6]

Adesso dovrebbe essere corretto

[P_1_6]

Algoritmo di Natale
17° Test di primalità e fattorizzazione di Lepore

[P_1_6]

mi dispiace aver sbagliato.
il tempo impiegato è 2^x dove x è la profondità dell'albero.
x dipende da come è composto il numero e non dalla dimensione delle cifre

[P_1_6]

Questa è la volta buona
https://www.academia.edu/36782326/Fatto ... _4_O_log_n_

[P_1_6]

#C #gmplibrary

Nuovo #Crivello sui #numeriPrimi in un qualsiasi intervallo

Gentilmente mi dareste qualche feedback su come migliorare il sorgente?

se p è un primo nella forma 12*x+5
allora questa scrittura
36*m^2+18*m+4*n^2+2*n+3=(p+1)/2
è unica con n ed m in Z
ed ho la dimostrazione

Congettura
se 12*x+5 non è primo
o non ci sono soluzioni
o ha più di una soluzione
o se ne ha una mcd(4*n+1,4*m+1)!=1


Credo la migliore implementazione possibile sia:
- prendo due numeri min e max in input (che sono le estremità dell'intervallo I dove voglio cercare primi)
- creo una matrice M[(max-min)/12][3] e la inizializzo a 0
- mi calcolo l'intervallo di m e per ogni m mi calcolo l'intervallo di n
- quindi per ogni coppia (m,n) nei rispettivi range mi calcolo P=2*d-1=2*(36*m^2+18*m+4*n^2+2*n+3)-1
- vado ad incrementare di 1 M[(P-min)/12][0] ,
-se è la prima volta memorizzo m in M[(P-min)/12][1] , memorizzo n in M[(P-min)/12][2]
- quando ho finito scorrerò la matrice e se questo valore M[0] == 1 farò GCD(4*(M[1])+1,4*(M[2])+1) e se GCD ==1 stamperò P=min+12*i



L'ho implementato in C con la libreria gmp-6.3.0 in questo modo:
al posto della matrice M ho creato tre array e li ho chiamati
M[][0] -> occurrences[]
M[][1] -> m[]
M[][2] -> n[]

prende un numero da input.txt
che è il minimo dell'intervallo definito da
#define interval_size 100 (cioè vede se 100 elementi nella forma 12*x+5 sono primi [si può anche incrementare interval_size])
e restituisce tutti i primi nella forma 12*x+5 in quell'intervallo
mi scuso se non ho usato allocazione dinamica della memoria

https://github.com/Piunosei/lepore_sieve_4/tree/main


la complessità dell'algoritmo che ho scritto è O(sqrt(max_interval)) in particolare è (sqrt(2*max_interval-1)-3)/6*J+a*GCD dove J in media è un po più grande di uno [a certe condizioni], dove a sono i potenziali primi che si scrivono in modo unico e GCD il tempo per il calcolo del massimo comun divisore

E' vero il tempo dell'algoritmo AKS è O((log p)^6) però per trovarne uno mentre per l'algoritmo che ho scritto io o ne trovi uno o 100000 è sempre O(sqrt(max_interval)) cambia poco [vedi immagini]

Quindi sqrt(p)<C*(log p)^6 dove C è il numero di interval_size si ha che se scegliamo C>sqrt(p)/[(log p)^6] il mio crivello è più veloce di AKS

[P_1_6]

https://www.academia.edu/121400171/Siev ... y_interval

[P_1_6]

vi segnalo questo algoritmo di fattorizzazione

riporto qualche mio test
non toccando max_a e max_c che si trovano all'interno del file di github della versione 2.3
che sono rispettivamente max_a=100 e max_c=20

Legenda
N è il numero da fattorizzare
P è un suo fattore
**************************
N = 20085107089
P= 100417
a=28
b=2
c=6

tempo 0m0.011s
cicli 20*100*2
**************************
N = 390644893234047643
P= 505928201
a=58
b=197
c=9

tempo 0m2.649s
cicli 20*100*197
**************************
N = 10000000012000000003591
P= 100000000063
a=78
b=6826
c=18

tempo 4m56.299s
cicli 20*100*6826
**************************

https://github.com/Piunosei/factorization_nr_138132535-

[LUBO-BACK]

vi segnalo questo algoritmo di fattorizzazione

riporto qualche mio test
non toccando max_a e max_c che si trovano all'interno del file di github della versione 2.3
che sono rispettivamente max_a=100 e max_c=20

Legenda
N è il numero da fattorizzare
P è un suo fattore
**************************
N = 20085107089
P= 100417
a=28
b=2
c=6

tempo 0m0.011s
cicli 20*100*2
**************************
N = 390644893234047643
P= 505928201
a=58
b=197
c=9

tempo 0m2.649s
cicli 20*100*197
**************************
N = 10000000012000000003591
P= 100000000063
a=78
b=6826
c=18

tempo 4m56.299s
cicli 20*100*6826
**************************

https://github.com/Piunosei/factorization_nr_138132535-

Non farò lo spiritoso perché ho visto che la cosa ti appassiona.

Io sono un matematico mancato, la scuola voleva che finissi a fare conti perché mi veniva facile e volevano pure farmi saltare un ciclo scolastico, ma io ero più interessato alle belle ragazze, che all'epoca non mi ricambiavano:) Così feci una diversa università. E per fortuna recuperai sul fronte ragazze. Dubito comunque che avrei sfondato come matematico, dopo un po' mi annoio.

Dopo questa divagazione, ti segnalo che ho però fatto un'elaborazione e posso comunicarti che, con questo approccio di sostanziale forza bruta, se tu dovessi trattare un numero con 50 cifre, tenendo conto del tuo pc (cioè di quello che hai usato per i test) ti ci vorrebbero oltre 91.000 anni.

I risultati discreti sui numeri piccoli sono merito dell'efficienza del C e della libreria GMP, ma il tuo approccio è forza bruta mascherata.

Con numeri seri questa illusione verrebbe meno. Certo, ci sono pc molto più veloci, ma anche algoritmi più efficienti.

Per ogni cifra in più, il tuo tempo di elaborazione è aumentato di 2,34 volte. Pensa solo alle potenze in base 2, per semplificare, e ti verranno i brividi. Già 2 alla 17 (che ti servirebbe per difetto per passare da 23 a 40) è 131072, ovvero ti ci vorrebbero quasi 900 giorni. In realtà di più perché era 2,34, ma è per capirci. Anche con pc straordinari, ritengo che ogni cifra in più richiederebbe lo stesso aumento proporzionale del tempo perché dipende dall'efficienza dell'algoritmo e non da altro.

La conosci la storiella degli inventore degli scacchi e dell'imperatore? https://www.scacchi360.it/sissa.php

La logica di base è quella, all'inizio raddoppiare i chicchi di riso sembra niente, poi le cose cambiano.

Esistono già algoritmi drammaticamente più efficienti. Però giocare coi numeri è divertente e provarci non fa male a nessuno:)

Perciò buona continuazione.

Ps: una piccola questione di metodo, se posso. E' vero che nelle scienze, talvolta, ci si imbatte in scoperte casuali come la penicillina od altro, ma in logica e matematica è piuttosto improbabile che, senza una teoria a monte, un sistema di calcolo possa rivelarsi effettivamente più veloce di un altro. Io mi concentrerei sulle premesse più che sulle prove empiriche.

[LUBO-BACK]

Guarda con yafu che non sfrutta la forza bruta

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


fac: factoring 10000000012000000003591
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
Total factoring time = 0.0090 seconds


***factors found***
P12 = 100000000057
P12 = 100000000063

***factorization:***
10000000012000000003591=100000000057*100000000063

ans = 1

[P_1_6]

ti ci vorrebbero quasi 900 giorni.

N = 27606985387162255149739023449107931668458716142620601169954803000803329
P= 170141183460469231731687303715884105727
a=2
b=8
c=18

real 0m49.932s
user 0m49.926s
sys 0m0.000s

[LUBO-BACK]

Con un surface go 2, perciò processore ridicolo

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


fac: factoring 27606985387162255149739023449107931668458716142620601169954803000803329
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 C71
rho: x^2 + 2, starting 1000 iterations on C71
rho: x^2 + 1, starting 1000 iterations on C71
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.185778 seconds
nfs: couldn't find special form
fac: job type determined to be siqs
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 C71, 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 C71, 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: 69/69 curves on C71, B1=50k, B2=gmp-ecm default, ETA: 0 sec

starting SIQS on c71: 27606985387162255149739023449107931668458716142620601169954803000803329

==== sieving in progress (1 thread): 14000 relations needed ====
==== Press ctrl-c to abort and save state ====
14060 rels found: 6758 full + 7302 from 74930 partial, (1954.30 rels/sec) ETA 0 sec)

SIQS elapsed time = 43.9100 seconds
Total factoring time = 45.9681 seconds


***factors found***
P33 = 162259276829213363391578010288127
P39 = 170141183460469231731687303715884105727

***factorization:***
27606985387162255149739023449107931668458716142620601169954803000803329=162259276829213363391578010288127*170141183460469231731687303715884105727

ans = 1

Detto questo, nei tuoi tempi c'è una linearità che non capisco, mi riguarderò il codice

[P_1_6]

Detto questo, nei tuoi tempi c'è una linearità che non capisco, mi riguarderò il codice

Se N è il numero da fattorizzare

MCD[(a^((b*N)^c-1)-1) mod (N) , N]=P

si basa tutto su questa espressione

UPDATE1:

un'altra ciliegina sulla torta (però sto usando numeri favorevoli all'algoitmo)

N = 3646154850295011369707131011438711095400799139943170490872585628683549034362552065955809589514611470241298944167703929337528884908857116141935206466329731087514964112054543019336536216107629523597606330154669196064144182472739556974502462402438903115845725630946428943768540714098264727068026730424033578827886916761701429264950573899186177
P= 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151
a=2
b=6
c=13

real 0m2.749s
user 0m2.744s
sys 0m0.004s

[LUBO-BACK]

Detto questo, nei tuoi tempi c'è una linearità che non capisco, mi riguarderò il codice

Se N è il numero da fattorizzare

MCD[(a^((b*N)^c-1)-1) mod (N) , N]=P

si basa tutto su questa espressione

Questo lo so, ma è un approccio di forza bruta, non euristico. Yafu ci mette 46 secondi e tu 49 minuti (e poi bisognerebbe vedere i rispettivi processori).

Quello che non capisco è l'incremento non lineare del tempo, bisognerebbe fare le prove con almeno un centinaio di numeri diversi per ogni lunghezza del numero iniziale per avere una media di riferimento stabile. Nei tuoi esempi di prima, ad ogni cifra aggiunta ci mettevi 2,34 volte di più, forse con più prove avresti avuti risultati diversi.

[P_1_6]

Detto questo, nei tuoi tempi c'è una linearità che non capisco, mi riguarderò il codice

Se N è il numero da fattorizzare

MCD[(a^((b*N)^c-1)-1) mod (N) , N]=P

si basa tutto su questa espressione

Questo lo so, ma è un approccio di forza bruta, non euristico. Yafu ci mette 46 secondi e tu 49 minuti (e poi bisognerebbe vedere i rispettivi processori).

Quello che non capisco è l'incremento non lineare del tempo, bisognerebbe fare le prove con almeno un centinaio di numeri diversi per ogni lunghezza del numero iniziale per avere una media di riferimento stabile. Nei tuoi esempi di prima, ad ogni cifra aggiunta ci mettevi 2,34 volte di più, forse con più prove avresti avuti risultati diversi.

sono 49 secondi

UPDATE1:
Processore Intel(R) Xeon(R) CPU E5-2630 0 @ 2.30GHz 2.30 GHz (2 processori)

[P_1_6]

Detto questo, nei tuoi tempi c'è una linearità che non capisco, mi riguarderò il codice

Se N è il numero da fattorizzare

MCD[(a^((b*N)^c-1)-1) mod (N) , N]=P

si basa tutto su questa espressione

UPDATE1:

un'altra ciliegina sulla torta (però sto usando numeri favorevoli all'algoitmo)

N = 3646154850295011369707131011438711095400799139943170490872585628683549034362552065955809589514611470241298944167703929337528884908857116141935206466329731087514964112054543019336536216107629523597606330154669196064144182472739556974502462402438903115845725630946428943768540714098264727068026730424033578827886916761701429264950573899186177
P= 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151
a=2
b=6
c=13

real 0m2.749s
user 0m2.744s
sys 0m0.004s

potresti provare con Yafu questo numero