View Single Post
Old 2021-10-26, 08:35   #20
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

10000010102 Posts
Default

#aiuto su #TeoriaDeiNumeri

Gentilmente qualcuno mi aiuterebbe su Teoria dei Numeri ?

tutte le variabili che nominerò sono interi


[Aiuto1]

E' vero che tutti i numeri nella forma N=4*((2^k)*w)+3
si possono esprimere in questa forma ?

4*((2^k)*x+1)^2-(2*((2^(k))*y)-1)^2

[Aiuto2]

E' vero che per trasformare un qualsiasi numero dispari in un numero nella forma N=4*((2^k)*w)+3 per un k scelto
si proceda in questo modo ?

se N-3 mod 2^(i+1) è diverso da 0 moltiplichi per N per 2^i+1

con i che parte da 1 ed arriva a k+1


[Aiuto3]

Questa relazione

4*((2^k)*x+1)^2>=4*((2^k)*x+1)^2-(2*((2^(k))*y)-1)^2>4*((2^k)*(x-1)+1)^2

ci dice quanto deve essere piccola y rispetto ad x conoscendo k

Si potrebbe creare un algoritmo di fattorizzazione che per ogni step di i+1 del secondo aiuto [Aiuto2]
se y verifica quella disequazione e si trova in O(1) il valore di x e quindi 2 fattori P e Q taliche P=p*s e Q=q*t
dove p e q sono i fattori del numero dispari iniziale e quindi facendo massimo comun divisore tra il numero iniziale e P o Q troveremmo p e q
il tutto aumentando i di un unità ad ogni step fino ad un k che ci riveli la fattorizzazione p*q ?


[Aiuto4]

Termina sicuramente l'algoritmo creato?
Qual è la complessità computazionale per fattorizzare un numero dispari N=p*q ?
E' forse casuale questa complessità?
Alberico Lepore is offline   Reply With Quote