Aiuto su Teoria Dei Numeri

[P_1_6]

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

[P_1_6]

Mi è venuto in mente questo altro algoritmo che aumenta computazionalmente ogni step però potrebbe essere utile per qualche numero

Input n //positive factorizable integer odd


N=n

int i = 1

int check = 0

while(1){
	if ( (N-3) mod (2^(i+1)) !=0 ){
		N=N*((2^i)+1)
		check=1
   	}
	a=(sqrt(N)-2)/(2*(2^i))
	x=(integer(a))+1
	y=1/2*(sqrt(4*((2^i)*x+1)^2-N)+1)
	if(IsInteger(y)){
		P=[(2*((2^i)*x+1))-(2*y-1)]   
		Q=[(2*((2^k)*x+1))+(2*y-1)]
		if( (P mod n)!=0 && (Q mod n)!=0){
			p=MCD(n,P)
			q=n/p
			return p & q
		}   
	}

	while (a>=1  && check == 1){   
		a=a/2
		x=(integer(a))+1   
		y=1/2*(sqrt(4*((2^i)*x+1)^2-N)+1)
		if(IsInteger(y)){
			P=[(2*((2^i)*x+1))-(2*y-1)]   
			Q=[(2*((2^k)*x+1))+(2*y-1)]
			if( (P mod n)!=0 && (Q mod n)!=0){
				p=MCD(n,P)
				q=n/p
				return p & q
			}   
		}
    
	}
check = 0
i=i+1

}


Output p & q

Credo nei prossimi giorni vedrò meglio quest'altra strada

"P_1_6":

Si potrebbe tentare quest'altra strada per portare $N$ nella forma $4*((2^b)*w)+3$

Trovare l'espressione di $z$ qui

$N*z=4*((2^b)*w)+3$ per un opportuno $b$

ed una volta calcolato $x$ da $4*((2^b)*x+1)^2=N*z$

tentare un ,spero piccolo, Bruteforce su $x$

[Studente Anonimo]

[xdom="Martino"]Io intanto chiudo. Mi sembra che hai ricevuto risposte a sufficienza.[/xdom]