Test di primalità e fattorizzazione di Lepore

[P_1_6]

Test di primalità e fattorizzazione di Lepore (ultimo)

Eravamo rimasti qui

Definizione
Tutti i numeri NR escluso i multipli di 2 e di 3 si scrivono nella forma 6h+1 e 6h+5.
Dimostrazione
NR modulo 6 =1 -> 6h+1
NR modulo 6 =2 -> è multiplo di 2
NR modulo 6 =3 -> è multiplo di 3
NR modulo 6 =4 -> è multiplo di 2
NR modulo 6 =5 -> 6h+1
NR modulo 6 =0 -> è multiplo di 2 e di 3

Lemma
Quindi partendo da 1 e facendo +2 e +4 si ha
1 5 7 11 13 17 19 23 25 29 ecc.ecc.

Definizione
Ogni numero NR escluso i multipli di 2 e di 3 si scrivono nella forma
1) X^2+6nX=NR
2) X^2+6nX+2X=NR
3) X^2+6nX+4X=NR
Dimostrazione
Dal lemma segue direttamente
1) X(X+6n)=NR
2) X(X+6n+2)=NR
3) X(X+6n+4)=NR

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
----------------------------------------------------------------------------------------
Da ciò si può dedurre che risolvendo (6h+1)*(6k+1)=6G+1
si possano risolvere gli altri tre casi
questi
(6h+1)*(6k+5)=6G+5
(6h+5)*(6k+1)=6G+5
moltiplicando per 5
e questo
(6h+5)*(6k+5)=6G+1
moltiplicando per 25
utilizzo questo per non scrivere quattro algoritmi diversi ma uno solo
----------------------------------------------------------------------------------
Per capire il ragionamento ci scriviamo in una tabella tutti gli NR generati da
X^2+6nX=NR
con x che parte da 1 e fa +6
cioè 1 7 13 19 35 31 37 43 ecc. ecc
e con n che parte da 1 e fa +1
cioè 1 2 3 4 5 6 ecc. ecc.
come in questa immagione



Supponiamo che il nostro NR sia 703=19*37
sqrt(703)=26,.....
quindi i possibili valori di q andranno da 31 a 703
mettiamoci più bassi e scegliamo 31 e analizziamo la sua diagonale come nell'immagine
vediamo che 775>703 e 589<703 quindi testiamo il 19 che è il nostro p
ma vediamo come muoverci se non lo becchiamo subito

scegliamo 931=19*43
sqrt(931)=30,.....
vediamo sempre più bassi e scegliamo 31 si può notare che il 775<931 quindi dobbiamo salire
quindi saliamo direttamente e scegliamo il 37 e vediamo che 1147>931 e 925<931 quindi testiamo il 25 che non è il nostro numero
quindi dovremo scendere e vedere il 31 che ci dice ma già lo abbiamo visto quindi passiamo a 43 che ci identifica proprio il 931

Ora vediamo più alti che succede
NR=589
prendiamo 43 e vediamo che 559<589 e 817>589 testiamo 13 e scendiamo
prendiamo 37 e 481<589 e 703>589 testiamo il 19 e scendiamo
prendiamo 31 che ci identifica proprio il 789

Ah dimenticavo per trovare i valori sulle diagonali
ad esempio l'incrocio 37 con 13 si fa 37*13=481

logaritmicamente ci troviamo i valori sulla diagonale
e logaritmicamente scendiamo e saliamo

Speranzoso di non aver commesso errori e in una vostra risposta cordialmente vi saluto
Alberico Lepore

[P_1_6]

Ho scoperto delle nuove cose:
(a) questa tabella è divisa in atomi
(b) funziona come lo snake (il gioco)
(c) se trovi la diagonale hai trovato il tesoro

(a) ogni numero di questa tabella è circondato da numeri e questa circonferenza compreso il numero stesso è ordinata
esempio 1333
è ordinato così 775 925 1075 1147 1333 1519 1591 1813 2035
esempio 91
è ordinato così 91 133 247 325

(b) ogni numero N di questa tabella è raggiungibile da un qualsiasi altro numero di questa tabella
si sceglie un numero e si guarda tutto l'atomo il valore più vicino al numero da cercare N sarà il fulcro del prossimo atomo fino ad arrivare al numero stesso N
esempio N=1333 e partiamo da ad esempio 91
la sequenza di fulcri sarà 91 325 703 1225 1075 1333
esempio 1375 e partiamo ad esempio da 775
la sequenza sarà 775 1333 1519 1225 1375

(c) ogni numero di questa tabella è identificato dalle regole di (b) con una diagonale
esempio 1891
la diagonale sarà 91 325 703 1225 1891
esempio 2035
la diagonale sarà 775 133 2035
esempio 1375
la diagonale sarà 133 403 817 1375


Speranzoso di non aver commesso errori e in una vostra risposta cordialmente vi saluto
Alberico Lepore

[P_1_6]

Algoritmo

Sia N=p*q con p , q ed N nella forma 6*h+1
Si troverà la fattorizzazione in al massimo logaritmo di [(N - F)/6] dove F è il primo numero dopo la radice quadrata di N nella forma 6*h+1.
Le regole del logaritmo:

scelto un G nell'intervallo [(N - F)/6, (N-1)/6] allora g=6*G+1
Testo se N modulo g = 0


se g*7 > N allora G deve scendere
altrimenti
se g*(g-6) < N allora G deve salire
altrimenti


se {N-{6*{parte inferiore di [(N/g)/6]}+1}*(g-6)} < {N-{6*{parte inferiore di [(N/g)/6]}+1}*(g+6)}&&
&& {N-{6*{parte inferiore di [(N/g)/6]}+1}*(g-6)} < {N-{6*{parte superiore di [(N/g)/6]}+1}*(g-6)}
&& {N-{6*{parte inferiore di [(N/g)/6]}+1}*(g-6)} < {N-{6*{parte superiore di [(N/g)/6]}+1}*(g+6)}
||
se {N-{6*{parte superiore di [(N/g)/6]}+1}*(g-6)} < {N-{6*{parte superiore di [(N/g)/6]}+1}*(g+6)}&&
&& {N-{6*{parte superiore di [(N/g)/6]}+1}*(g-6)} < {N-{6*{parte inferiore di [(N/g)/6]}+1}*(g-6)}
&& {N-{6*{parte superiore di [(N/g)/6]}+1}*(g-6)} < {N-{6*{parte inferiore di [(N/g)/6]}+1}*(g+6)}

allora G deve scendere
altrimenti

G deve salire

[Pappappero]

Ho letto solo l'ultimo post, che mi sembra molto meglio di tutti gli altri che sono incomprensibili (almeno per me).

Se spieghi cosa vuol dire 'deve scendere' e 'deve salire' e fornisci un modo determistico di scegliere $G$, quello che hai scritto nell'ultimo post sembra quasi un algoritmo. Poi c'e' da vedere se funziona e se ha la complessita' che dici.

[P_1_6]

grazie pappappero
cercherò di spiegarmi meglio (almeno ci provo)

Ennesimo test di fattorizzazione di Lepore in log


Per capire ci scriviamo una tabella dove i valori cerchiati sono i valori G=(N-1)/6
di questa tabella


cioè questa


i numeri di fianco a due cerchiati sono la differenza dei due numeri cerchiati
si deduce facilmente che $n+(8+6*n)*a+6*a*(a-1)=G$
dove a=(x-1)/6 per N=x*y
e n è x^2+6*n*x=N

prendiamo ad esempio il numero N=1705 quindi G=284 dobbiamo trovare il valore 80
una volta trovato 80 allora troveremo 1225=(x-6)^+6*n*(x-6) e 1705=x^2+6*n*x facciamo il sistema e lo fattorizziamo.
Ora viene quello difficile da spiegare (ci provo)

se prendiamo un valore anche di poco più grande di 80 ad esempio 92
vi faccio vedere che succede 92+80+68=240 e dobbiamo fermarci perchè aggiungendo 56 supereremo il 284
quindi n dovrebbe essere n=284-240=44 e a=3
ma sappiamo che n=(G-6*a^2-2a)/(6*a+1)=11,78...
per farle combaciare le due n significa che dovrebbe scendere il 44
che significa che a dovrebbe salire quindi 92 non va bene ed abbiamo bisogno di un valore più basso

un 'avvertenza
con i numeri bassi se scegliamo come nell'esempio al posto di 80, il 68 non si arriverà mai al 284

[Pappappero]

Non devi prendere un esempio. Devi scrivere un algoritmo.

[P_1_6]

Hey c'ho provato ma non so se l'ho scritto bene


Algoritmo di fattorizzazione

Sia N=p*q nella forma N=6*G+1 e p=6*a+1 e q=6b+1

Sia G=(N-1)/6
sia A un numero
Se G è dispari A è nella forma 12*k+2
Se G è pari A è nella forma 12*h+8
A è compreso nell'intervallo [8,G] //il valore G è da rivedere però non fa niente

Scelto un A in [8,G](supponiamo con G pari)
dobbiamo sottrarre a G la somma dei numeri A+(A-12)+(A-24)+(A-36)......
fino ad arrivare all'ultimo numero positivo
il numero di questi numeri sarà la nostra ipotetica a
(siccome ho trovato che A+6=p+q)
facciamo q=A+6-(6*a+1)

Se gli ipotetici p*q == N abbiamo trovato i valori p e q reali
Se gli ipotetici p*q < N dobbiamo far scendere il valore di A
Se gli ipotetici p*q > N dobbiamo far salire il valore di A

[Pappappero]

Proviamo cosi'.

Input: $N$ della forma $N = pq$ con $p,q \equiv 1 \mod 6$.
Output: $p,q$.

1. Definisco $G = (N-1)/6$;
2.

- se $G$ e' dispari, definisco $A$ che sia pari e il piu' vicino possibile a $(G-8)/2$(perche' ho in mente di partire dal centro dell'intervallo...o vuoi partire da un'altra parte? o vuoi fare un algoritmo non deterministico? boh)
- se $G$ e' dispari, definisco $A$ che sia congruo a $2$ modulo $6$ e il piu' vicino possibile a $(G-8)/2$

3 Poi ?

[P_1_6]

247
G=41
i possibili A sono 14 26 38
li faccio tutti e tre
per il 14
41-14-2
a=2
p=14+6-13=7
p*(6*a+1)=91<247

per il 26
41-26-14
a=2
p=26+6-13
p*(6*a+1)=247=247

per il 38
41-38
a=1
p=38+6-7=37
p*(6*a+1)=259>247

EDIT:Non i preoccupare è tutto regolare
nel caso A=14 come noti c'è un anomalia che si risolve con la teoria
e
nel caso 38 devo ancora scegliere l'intervallo come ti ho già detto

mi spiego meglio vedi sul caso A=14

per il 26
41-26-14
a=2
p=26+6-13
p*(6*a+1)=247=247
vedi il 14 di 41-26-14
bene questo 14=6*n+8 dove n è la n di p^2+6*n*p=247
quindi
vedi
41-14-2
significherebbe 6*n+8=2 cioè n < 0 impossibile
quindi per quanto riguarda l'algoritmo
se G è dispari e si arriva a 2 dobbiamo far salire la A
se G è pari e si arriva a 8 dobbiamo controllare p^2=N e p non è intero far salire la A

per quanto riguarda l'intervallo [8,G] mi prendo un po di tempo per capire meglio

L'intervallo dovrebbe essere questo se non ho commesso errori
[ 8 , (7*(6*parteinterainferioredi((N/7)/6)+1)-1)/6 - (parteinterainferioredi((N/7)/6)-1)]
cioè per il 247 sarà [8,32]

[P_1_6]

supponiamo di voler fattorizzare un numero N
G=(N-1)/6
supponiamolo pari quindi A è nella forma A=6h+8

partiamo da 8 e logaritmicamente ci calcoliamo l'ipotetica c
(cioè quante volte dobbiamo fare +12 per arrivare a G )
e controlliamo
(6*a+1)^2+*n*(6*a+1)=N
(6*(a-c-1)+1)^2+*n*(6*(a-c-1)+1)=6*W+1
dove W=G-S
dove S=8*(c+1)+12*(c*(c+1))/2

raddoppiamo il valore di 8 e prendiamo il valore 20

e reiteriamo il procedimento stando attenti a non superare il doppio nelle scelte successive
quindi scegliamo il 32
poi il 56
poi il 104
poi il 200

Questo metodo dovrebbe funzionare al 100%

Esempio N=3397
G=(3397-1)/6=566

per 8 niente
per 20 niente
per 32 niente
vediamo per 56
c=5
S=56*6+6*30=516
W=566-516=50
6*50+1=301

quindi il sistema
(6*a+1)^2+6*n*(6*a+1)=N
(6*(a-5-1)+1)^2+6*n*(6*(a-5-1)+1)=301


Grazie per l'attenzione