Algoritmi sui numeri primi.

[GURUGU]

Scusami, ma tu stai proprio male; la parte "about me" del tuo blog fa spisciare

[P_1_6]

Non sapevo che scrivere. Ho fatto un test in rete e ho avuto questa risposta.

[caturen]

allora si, stai proprio male

[P_1_6]

NON CORRETTO .
L'algoritmo corretto si trova qui:
http://forum.ubuntu-it.org/viewtopic.ph ... 0#p4753150



Vorrei un vostro parere su questo procedimento per determinare la fattorizzazione o la primalità di un numero in tempi logaritmici.

Vorrei un vostro parere su questo procedimento per determinare la fattorizzazione o la primalità di un numero in tempi logaritmici.

Fattorizzazione e test di primalità di Lepore-Santo in 4*log[(Y-X)/6]+1
Vi mostrerò l’esempio base cioè la fattorizzazione di due numeri primi perchè reiterando il processo si può fattorizzare qualsiasi tipo di numero.
Ogni numero NR (non muliplo di 2 e di 3 ) diviso sei da come decimali 1666p e 8333p (p sta per periodico) poichè per ogni NR modulo sei si avrà

1/6= 0,1666p

il 2 è divisibile per 2

il 3 divisibile per 3

il 4 divisibile per 2

5/6=0,8333p

il 6 divisibile per 2 e per 3

e ciò equivale a dire che partendo da 1 si deve fare una volta +4 una volta +2 e quindi l’insieme dei numeri non muliplo di 2 e di 3 sarà:

1
1+4=5
5+2=7
7+4=11
11+2=13
13+4=17
17+2=19
19+4=23
23+2=25
25+4=29
29+2=31
…..
…..
ecc.ecc.

quindi si può vedere questo:

5*5; 25+(1*30) ; 25+(2*30); 25+(3*30); ecc.
5*7; 35+(1*30) ; 35+(2*30); 35+(3*30); ecc.
7*7; 49+(1*42); 49+(2*42); ecc. ecc.
7*11; 77+(1*42); 77+(2*42); ecc. ecc.

Da ciò possiamo ricavare le tre equazioni:

X^2+n*(X*6)=NR
X*(X+2)+n(X*6)=NR
X*(X+4)+n(X*6)=NR

dove n=(Y-X)/6 nella prima equazione
n=(Y-X-2)/6 nella seconda equazione
n=(Y-X-4)/6 nella terza equazione

Quindi se troviamo il valore di n troviamo X.

L’idea è quella di dividere per 2 la n fino ad arrivare ad n=1 (cioè testare per n=1 se l’equazione trasformata da risultati).
Se n è pari va bene così, se n è dispari dobbiamo togliere 1 e dividere per due.

Come funziona l’algoritmo.

Prendiamo in considerazione 6001=17*357
Siccome 6001/6=1000,1666p e quindi ha come parte decimale 1666p useremo la prima equazione, infatti:
X^2+n*(X*6)=6001
ed n=56
Non vi preoccupate se non capite come faccio a sapere se n è dipari o pari lo dirò più in là.
quindi
56/2=28
28/2=14
14/2=7 quindi 7-1=6
6/2=3 quindi 3-1=2
2/1=1

quindi la sequenza è
Pari
P
P
Dispari
D

Quindi modificheremo X^2+n*(X*6)=6001 in
X^2+n*(X*12)=6001
X^2+n*(X*24)=6001
X^2+n*(X*48)=6001
Ci troviamo nel dispari quindi togliere 1 alla n che significa aggiungere X*48 in più dividere per 2 cioè
X^2+n*(X*96)+48X=6001
ancora dispari quindi
X^2+n*(X*192)+96X+48X=6001 che meglio scritta è
X^2+n*(X*192)+144X=6001 per n=1
X^2+(X*336)=6001 si avrà X=17

Ora vediamo come facciamo a decidere se n è pari o è dipari

portiamo l’equazione nella forma

n*X=(6001 – X^2)/6

La parte a sinistra è uguale alla parte di destra quindi se è pari una è pari anche l’altra , se è dipari una è dispari anche l’altra.

Dobbiamo considerare che X è sempre dispari quindi n*X sarà pari se n è pari e sarà dispari se n è dipari.

Vediamo con un esempio il procedimento.

6001/6=1000,166p

(X^2)/6=k,1666 perchè i quadrati sono sempre in questa forma

Quindi togliamo 0,1666p a 1000,1666p e lo togliamo a K,1666p che diventerà k

quindi avremmo 1000-k che è un intero ed è da valutare se è pari o è dispari

noi dobbiamo trovare i valori interi di n

Quindi l’equazione x^2 + n*(6x) = 6001

k è sempre pari perchè

x^2=(6h+5)^2=36h^2+60h+25

oppure

x^2=(6h+1)^2=36h^2+12h+1

ad entrambe se togliete 1 e dividete per 6 sono pari
ne segue

quindi 1000-k è pari e quindi n è pari
Quindi la nuova equazione sarà x^2 + n*(12x) = 6001

1) se n(i) è dispari e NR(i) è dispari e k(i) è pari dobbiamo sottrarre 3 ad NR(i) e 2 a k(i) poi dividere per 2 n(i)

2) se n(i) è dispari e NR(i) è pari e k(i) è dispari dobbiamo sottrarre 2 ad NR(i) ed 1 a k(i) e poi dividere per 2 n(i)

3) se n(i) è pari e NR(i) è dispari e k(i) è dispari dobbiamo sottrarre 1 ad NR(i) ed 1 a k(i) e poi dividere per 2 n(i)

Quando serve la forza bruta io la uso.

Quindi usiamo entrambe le a) e b) e uso i valori pari e dispari di h per entrambe.

a) x^2=(6h+5)^2=36h^2+60h+25

b) x^2=(6h+1)^2=36h^2+12h+1

n

a.1) 1000 – 6h^2+10h+4=P

b.1) 1000 – 6h^2+2h=P
n/2
1.a) h=D 500-h(3h+5)+2=P

1.b) h=P 500-h(3h+5)+2=P

1.c) h=D 500-h(3h+1)=D per la 2)dobbiamo sottrarre 2 a 500 e 1 a k

1.d) h=P 500-h(3h+1)=P
n/4

2.a) h=D 250-h*(1/2)*(3h+5)+1=P

2.b) h=P 250-h*(1/2)*(3h+5)+1=P=12

2.c) h=D 249-h*(1/2)*(3h+1)-(1/2)=249-(1/2)(h(3h+1))=D per la 3)dobbiamo sottrarre 3 a 249 e 2 a k

2.d) h=P 250-h*(1/2)*(3h+1)=D per la 2)dobbiamo sottrarre 2 a 250 e 1 a k
ecc.ecc.

Tra qualche giorno posto molti esempi.

————————————————————————————————————————————————————-

Per i casi NR/6=k,83333 ci si comporta analogamente.

(NR^2)/6=H,1666

l’equazione diventerà: Z^2+n*(Z*6)=NR dove Z=X^2

procediamo normalmente per Z , e X=radicequadrata(Z).

The time taken will 4*log{[(Y-X)^2]/6}+1


Alberico Lepore, Ruggiero Santo 25/04/2015

[P_1_6]

Ho postato la soluzione finale potete darmi un parere?
grazie in anticipo per le vostre opinioni

[Zoff]

Visto che tratti gli stessi argomenti accodo questa discussione all'altra che avevi creato: http://forum.ubuntu-it.org/viewtopic.php?f=67&t=591563

[Zoff]

Siccome 6001/6=1000,1666p e quindi ha come parte decimale 1666p useremo la prima equazione, infatti:
X^2+n*(X*6)=6001
ed n=56

Come selezioni 56 visto che l'equazione X^2+n*(X*6)=6001 ha infinite soluzioni, tutte date da una di queste due (essendo una equazione di secondo grado) soluzioni letterali?


Link alla soluzione su wolfram: http://goo.gl/yKoe5b

[P_1_6]

mi trovo i pari e i dispari P-P-P-D-D
nel frattempo ad ogni step trasformo l'equazione e provo per n =1
ad un certo punto l'equazione trasformata per n=1 è questa
X^2+(X*336)=6001 ->X=17
a questo punto volendo mi posso ricavare il 56
1*D=3
3*D=7
7*P=14
14*P=28
28*P=56
ma ricavare il 56 non serve a nulla in quanto ho già trovato X=17

[Zoff]

Assolutamente no, 17 lo ricavi partendo da 56 perché per poter selezionare "X^2+(X*336)=6001 ->X=17" ti serve la sequenza P P P D D e la sequenza la trovi partendo da 56.

Quindi rinnovo la domanda, come selezioni 56?

[P_1_6]

ho spiegato prima la teoria

56/2=28
28/2=14
14/2=7 quindi 7-1=6
6/2=3 quindi 3-1=2
2/1=1

quindi la sequenza è
Pari
P
P
Dispari
D

Quindi modificheremo X^2+n*(X*6)=6001 in
X^2+n*(X*12)=6001
X^2+n*(X*24)=6001
X^2+n*(X*48)=6001
Ci troviamo nel dispari quindi togliere 1 alla n che significa aggiungere X*48 in più dividere per 2 cioè
X^2+n*(X*96)+48X=6001
ancora dispari quindi
X^2+n*(X*192)+96X+48X=6001 che meglio scritta è
X^2+n*(X*192)+144X=6001 per n=1
X^2+(X*336)=6001 si avrà X=17

e poi la pratica

Ora vediamo come facciamo a decidere se n è pari o è dipari

portiamo l’equazione nella forma

n*X=(6001 – X^2)/6

La parte a sinistra è uguale alla parte di destra quindi se è pari una è pari anche l’altra , se è dipari una è dispari anche l’altra.

Dobbiamo considerare che X è sempre dispari quindi n*X sarà pari se n è pari e sarà dispari se n è dipari.

Vediamo con un esempio il procedimento.

6001/6=1000,166p

(X^2)/6=k,1666 perchè i quadrati sono sempre in questa forma

Quindi togliamo 0,1666p a 1000,1666p e lo togliamo a K,1666p che diventerà k

quindi avremmo 1000-k che è un intero ed è da valutare se è pari o è dispari

noi dobbiamo trovare i valori interi di n

Quindi l’equazione x^2 + n*(6x) = 6001

k è sempre pari perchè

x^2=(6h+5)^2=36h^2+60h+25

oppure

x^2=(6h+1)^2=36h^2+12h+1

ad entrambe se togliete 1 e dividete per 6 sono pari
ne segue

quindi 1000-k è pari e quindi n è pari
Quindi la nuova equazione sarà x^2 + n*(12x) = 6001

1) se n(i) è dispari e NR(i) è dispari e k(i) è pari dobbiamo sottrarre 3 ad NR(i) e 2 a k(i) poi dividere per 2 n(i)

2) se n(i) è dispari e NR(i) è pari e k(i) è dispari dobbiamo sottrarre 2 ad NR(i) ed 1 a k(i) e poi dividere per 2 n(i)

3) se n(i) è pari e NR(i) è dispari e k(i) è dispari dobbiamo sottrarre 1 ad NR(i) ed 1 a k(i) e poi dividere per 2 n(i)

Quando serve la forza bruta io la uso.

Quindi usiamo entrambe le a) e b) e uso i valori pari e dispari di h per entrambe.

a) x^2=(6h+5)^2=36h^2+60h+25

b) x^2=(6h+1)^2=36h^2+12h+1

n

a.1) 1000 – 6h^2+10h+4=P

b.1) 1000 – 6h^2+2h=P
n/2
1.a) h=D 500-h(3h+5)+2=P

1.b) h=P 500-h(3h+5)+2=P

1.c) h=D 500-h(3h+1)=D per la 2)dobbiamo sottrarre 2 a 500 e 1 a k

1.d) h=P 500-h(3h+1)=P
n/4

2.a) h=D 250-h*(1/2)*(3h+5)+1=P

2.b) h=P 250-h*(1/2)*(3h+5)+1=P=12

2.c) h=D 249-h*(1/2)*(3h+1)-(1/2)=249-(1/2)(h(3h+1))=D per la 3)dobbiamo sottrarre 3 a 249 e 2 a k

2.d) h=P 250-h*(1/2)*(3h+1)=D per la 2)dobbiamo sottrarre 2 a 250 e 1 a k
ecc.ecc.

[Zoff]

Non hai risposto alla domanda, dai per assodato che n=56 come soluzione di X^2+n*(X*6)=6001 ma è solo UNA soluzione e non spieghi perché la scegli, tutti i passaggi successivi dipendono da questa scelta.
Infatti la prima riga dalla tua ultima risposta parte con: 56/2=28

Puoi spiegare perché scegli 56? Se no, pazienza, semplicemente l'algoritmo NON funziona.

PS: Non esiste teoria nella tua descrizione, fai sempre e solo esempi numerici.

[P_1_6]

allora non conosciamo il 56, ok.
E inizia da quà

Quindi usiamo entrambe le a) e b) e uso i valori pari e dispari di h per entrambe.

a) x^2=(6h+5)^2=36h^2+60h+25

b) x^2=(6h+1)^2=36h^2+12h+1

[Zoff]

Come arriviamo a quelle formule se non conosciamo 56?

[P_1_6]

vedo questa
n*X=(6001 – X^2)/6

vedo questo

x^2=(6h+5)^2=36h^2+60h+25

oppure

x^2=(6h+1)^2=36h^2+12h+1

ad entrambe se togliete 1 e dividete per 6 sono pari

poi faccio questo

n*X=(6001 – X^2)/6 -> n*X=1000- k dove k=(X^2)-1

come ho spiegato qui

n*X=(6001 – X^2)/6

La parte a sinistra è uguale alla parte di destra quindi se è pari una è pari anche l’altra , se è dipari una è dispari anche l’altra.

Dobbiamo considerare che X è sempre dispari quindi n*X sarà pari se n è pari e sarà dispari se n è dipari.

Vediamo con un esempio il procedimento.

6001/6=1000,166p

(X^2)/6=k,1666 perchè i quadrati sono sempre in questa forma

Quindi togliamo 0,1666p a 1000,1666p e lo togliamo a K,1666p che diventerà k

quindi avremmo 1000-k che è un intero ed è da valutare se è pari o è dispari

poi faccio questo

1) se n(i) è dispari e NR(i) è dispari e k(i) è pari dobbiamo sottrarre 3 ad NR(i) e 2 a k(i) poi dividere per 2 n(i)

2) se n(i) è dispari e NR(i) è pari e k(i) è dispari dobbiamo sottrarre 2 ad NR(i) ed 1 a k(i) e poi dividere per 2 n(i)

3) se n(i) è pari e NR(i) è dispari e k(i) è dispari dobbiamo sottrarre 1 ad NR(i) ed 1 a k(i) e poi dividere per 2 n(i)

Quando serve la forza bruta io la uso.

Quindi usiamo entrambe le a) e b) e uso i valori pari e dispari di h per entrambe.

a) x^2=(6h+5)^2=36h^2+60h+25

b) x^2=(6h+1)^2=36h^2+12h+1

n

a.1) 1000 – 6h^2+10h+4=P

b.1) 1000 – 6h^2+2h=P
n/2
1.a) h=D 500-h(3h+5)+2=P

1.b) h=P 500-h(3h+5)+2=P

1.c) h=D 500-h(3h+1)=D per la 2)dobbiamo sottrarre 2 a 500 e 1 a k

1.d) h=P 500-h(3h+1)=P
n/4

2.a) h=D 250-h*(1/2)*(3h+5)+1=P

2.b) h=P 250-h*(1/2)*(3h+5)+1=P=12

2.c) h=D 249-h*(1/2)*(3h+1)-(1/2)=249-(1/2)(h(3h+1))=D per la 3)dobbiamo sottrarre 3 a 249 e 2 a k

2.d) h=P 250-h*(1/2)*(3h+1)=D per la 2)dobbiamo sottrarre 2 a 250 e 1 a k
ecc.ecc.

spero di essere stato chiaro

[Zoff]

"vedo questo" non mi sembra che spieghi come ci si arrivi.

Quindi rinnovo la domanda, come arrivi a "n*X=(6001 – X^2)/6" e alle seguenti due espressioni?

Codice: Seleziona tutto

x^2=(6h+5)^2=36h^2+60h+25

oppure

x^2=(6h+1)^2=36h^2+12h+1

conoscendo solo 6001?

Comunque per dimostrare che il tuo algoritmo funziona è molto semplice, scrivilo in un qualsiasi linguaggio di programmazione.
E produci un programma in grado di eseguire automaticamente i passaggi dell'algoritmo.

[P_1_6]

X^2+n*(X*6)=6001 è la stessa cosa di questa "n*X=(6001 – X^2)/6"

poi quelle due
siccome X/6=h,16666 oppure X/6=h,83333
significa che X=6h+1 oppure X=6h+5

purtroppo non so programmare

[Zoff]

Quindi vediamo di riassumenre, dopo la tua affermazione:

allora non conosciamo il 56, ok.
E inizia da quà

Quindi usiamo entrambe le a) e b) e uso i valori pari e dispari di h per entrambe.

a) x^2=(6h+5)^2=36h^2+60h+25

b) x^2=(6h+1)^2=36h^2+12h+1

Il tuo "Come funziona l'algoritmo" diventa:

Come funziona l’algoritmo.

Prendiamo in considerazione 6001=17*357

[..parte omessa su tua dichiarazione...]

Quindi usiamo entrambe le a) e b) e uso i valori pari e dispari di h per entrambe.

a) x^2=(6h+5)^2=36h^2+60h+25

b) x^2=(6h+1)^2=36h^2+12h+1

n

a.1) 1000 – 6h^2+10h+4=P

b.1) 1000 – 6h^2+2h=P
n/2
1.a) h=D 500-h(3h+5)+2=P

1.b) h=P 500-h(3h+5)+2=P

1.c) h=D 500-h(3h+1)=D per la 2)dobbiamo sottrarre 2 a 500 e 1 a k

1.d) h=P 500-h(3h+1)=P
n/4

2.a) h=D 250-h*(1/2)*(3h+5)+1=P

2.b) h=P 250-h*(1/2)*(3h+5)+1=P=12

2.c) h=D 249-h*(1/2)*(3h+1)-(1/2)=249-(1/2)(h(3h+1))=D per la 3)dobbiamo sottrarre 3 a 249 e 2 a k

2.d) h=P 250-h*(1/2)*(3h+1)=D per la 2)dobbiamo sottrarre 2 a 250 e 1 a k
ecc.ecc.

Dov'è che ricavi 17 e 357 con complessità polinomiale?
No perché 17*357=6069, 6001 è 17*353=6001, mi chiedo come hai fatto a produrre un "esempio" partendo da valori sbagliati.

[P_1_6]

vabbè è un errore di battitura

poi c'è un altro errore

in effetti questa è sbagliata

1.c) h=D 500-h(3h+1)=D per la 2)dobbiamo sottrarre 2 a 500 e 1 a k

è sbagliata
è 500-P=P

di conseguenza questa

2.c) h=D 249-h*(1/2)*(3h+1)-(1/2)=249-(1/2)(h(3h+1))=D per la 3)dobbiamo sottrarre 3 a 249 e 2 a k

diventa

2.c) 250-h(3h+1)*1/2=250-h*[(3*(h/2))+1/2]=250-h*[(h+h/2)+1/2]=250-h*(h+1+h)/2=non intero quindi impossibile poichè 500-P=P

scusatemi se commetto errori

[Zoff]

A me piacerebbe vedere un esempio COMPLETO.
Per intenderci un esempio in cui parti da un numero generato dal prodotto di due numeri primi in cui fai vedere TUTTI i passaggi fino ad ottenere i primi generanti.

[P_1_6]

ok per stasera lo posto correttamente per intero
grazie per le tue opinioni