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à?