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

[hydro1]

"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$

Certo, ti stai chiedendo se l'equazione $n=x^2-y^2$ è risolubile con $n\equiv 3\mod 4$, $x$ pari e $y\equiv 1\mod 4$. Basta porre \(x=(n+1)/2\) e \(y=(1-n)/2\).

"P_1_6":
[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 ?

Questa domanda non significa nulla, non tutti i numeri dispari sono $3$ modulo $4$.

[P_1_6]

"hydro":[quote="P_1_6"]
[quote="P_1_6"]
[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 ?

Questa domanda non significa nulla, non tutti i numeri dispari sono $3$ modulo $4$.[/quote][/quote]

intendo trasformare $4*h+1$ in $4*(2^k)+3$

ad esempio vuoi trasformare un numero fino a $k=3$ ad esempio il numero iniziale è $25$
$25-3 mod 2^(1+1) =2 !=0$ moltiplico per $(2^1)+1=3$
$75-3 mod 2^(2+1) =0$ non moltiplico per niente
$75-3 mod 2^(3+1) =8 !=0$ moltiplico per $(2^3)+1=9$
$675=4*(2^3*h)+3$

e cioè seguendo questa regola

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

[hydro1]

Puoi fare quello che vuoi, che significa "trasformare un numero in un altro"?? Non si capisce proprio quale sia la domanda. Sembra che tu abbia un qualche algoritmo ma a) non si capisce quale sia e b) anche fosse, qual è la domanda?

[P_1_6]

"hydro":Puoi fare quello che vuoi, che significa "trasformare un numero in un altro"?? Non si capisce proprio quale sia la domanda. Sembra che tu abbia un qualche algoritmo ma a) non si capisce quale sia e b) anche fosse, qual è la domanda?

Il tutto è legato alla fattorizzazione che giustamente come dici tu chi inizia a leggere non capisce, perciò moltiplico e non sottraggo o aggiungo o (*)divido

[P_1_6]

"hydro":Puoi fare quello che vuoi, che significa "trasformare un numero in un altro"?? Non si capisce proprio quale sia la domanda. Sembra che tu abbia un qualche algoritmo ma a) non si capisce quale sia e b) anche fosse, qual è la domanda?

Questo dovrebbe essere l'algoritmo

input n //positive integer odd


N=n

int i = 1

while(1){
	if ( (N-3) mod (2^(i+1)) !=0 ){
		N=N*((2^i)+1)
	}
	a=(sqrt(N)-2)/(2*(2^i))
	x=(integer(a))
	if(x != a){
		x=x+1
	}
	y=1/2*(sqrt(4*((2^i)*x+1)^2-N)+1)
	if(y== integer(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
			break
	}

i++;

}

E la domanda è :
ci sarà sempre un break per ogni n fattorizzabile?

Qual'è il costo computazionale per la fattorizzazione di n ?

[hydro1]

Un consiglio: nessuno leggerà mai quel codice. Devi descrivere a parole, e soprattutto in modo chiaro e non ambiguo, qual è l'input, quali sono gli step, e qual è l'output. Ti faccio un esempio. Il metodo di Fermat funziona così: l'input è un intero positivo $N$. L'algoritmo fa la cosa seguente: calcola $\sqrt{N}$, la arrotonda per eccesso trovando un intero $a$ e poi calcola $a^2-N$. Se questo è un quadrato $b^2$, l'algoritmo termina perchè $a-b$ è un fattore non banale di $N$, ed è l'output dell'algoritmo. Altrimenti, si ripete incrementando $a$ di 1, e così via. Ovviamente l'algoritmo termina al più quando $a=N$.

[P_1_6]

"hydro":Un consiglio: nessuno leggerà mai quel codice. Devi descrivere a parole, e soprattutto in modo chiaro e non ambiguo, qual è l'input, quali sono gli step, e qual è l'output. Ti faccio un esempio. Il metodo di Fermat funziona così: l'input è un intero positivo $N$. L'algoritmo fa la cosa seguente: calcola $\sqrt{N}$, la arrotonda per eccesso trovando un intero $a$ e poi calcola $a^2-N$. Se questo è un quadrato $b^2$, l'algoritmo termina perchè $a-b$ è un fattore non banale di $N$, ed è l'output dell'algoritmo. Altrimenti, si ripete incrementando $a$ di 1, e così via. Ovviamente l'algoritmo termina al più quando $a=N$.

Input n //positive factorizable integer odd


N=n

int i = 1

while(1){
   if ( (N-3) mod (2^(i+1)) !=0 ){
      N=N*((2^i)+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
         break
      }	
   }

i++;

}


Output p & q

Input : un numero dispari fattorizzabile

partiamo da $i =1$

$step1$ : portiamo l'input nella forma $N=4*((2^i)*w)+3$ questo modo:
se $N-3 mod 2^(i+1)$ è diverso da $0$ moltiplichi $N$ per $2^i+1$ e cioè $N=N*(2^i+1)$

Se la nostra $y$ verifica questa disequazione
$4*((2^i)*x+1)^2>=4*((2^i)*x+1)^2-(2*y-1)^2=N>4*((2^i)*(x-1)+1)^2$
significa che $N$ è compreso li in mezzo

$step2$ : ci calcoliamo $x$ in questo modo da $4*((2^i)*a+1)^2=N$
$->$ $a=(sqrt(N)-2)/(2*(2^i))$
$x=($integer$(a))+1$
dove integer$(a)$ significa partei ntera inferiore di $a$

$step3$ : ci calcoliamo da $4*((2^i)*x+1)^2-(2*y-1)^2=N$ la $y$
$y=1/2*(sqrt(4*((2^i)*x+1)^2-N)+1)$

$step4$ : se IsInteger$(y)$ e cioè se $y$ è un intero significa che avremo una qualsiasi fattorizzazione dell'$N$
trasformato fino a questo momento nella fattorizzazione $P*Q$
dove $P=[(2*((2^i)*x+1))-(2*y-1)]$ ; $Q=[(2*((2^i)*x+1))+(2*y-1)]$

$step5$ : Se $P=s*p$ e $Q=t*q$ dove $p$ e $q$ sono i fattori iniziali dell'input $n$
allora $p=MCD(n,P)$ ; $q=n/p$

se lo $step5$ è vero allora $break$ [hai finito] altrimenti incrementa $i$ di una unità e riparti dallo $step1$

[hydro1]

"P_1_6":
Input : un numero dispari fattorizzabile

partiamo da $i =1$

$step1$ : portiamo l'input nella forma $N=4*((2^i)*w)+3$ questo modo:
se $N-3 mod 2^(i+1)$ è diverso da $0$ moltiplichi $N$ per $2^i+1$ e cioè $N=N*(2^i+1)$

Se la nostra $y$ verifica questa disequazione
$4*((2^i)*x+1)^2>=4*((2^i)*x+1)^2-(2*y-1)^2=N>4*((2^i)*(x-1)+1)^2$
significa che $N$ è compreso li in mezzo

$step2$ : ci calcoliamo $x$ in questo modo da $4*((2^i)*a+1)^2=N$
$->$ $a=(sqrt(N)-2)/(2*(2^i))$
$x=($integer$(a))+1$
dove integer$(a)$ significa partei ntera inferiore di $a$

$step3$ : ci calcoliamo da $4*((2^i)*x+1)^2-(2*y-1)^2=N$ la $y$
$y=1/2*(sqrt(4*((2^i)*x+1)^2-N)+1)$

$step4$ : se IsInteger$(y)$ e cioè se $y$ è un intero significa che avremo una qualsiasi fattorizzazione dell'$N$
trasformato fino a questo momento nella fattorizzazione $P*Q$
dove $P=[(2*((2^i)*x+1))-(2*y-1)]$ ; $Q=[(2*((2^i)*x+1))+(2*y-1)]$

$step5$ : Se $P=s*p$ e $Q=t*q$ dove $p$ e $q$ sono i fattori iniziali dell'input $n$
allora $p=MCD(n,P)$ ; $q=n/p$

se lo $step5$ è vero allora $break$ [hai finito] altrimenti incrementa $i$ di una unità e riparti dallo $step1$

Ok ci rinuncio, continua a capirsi molto poco. Spuntano fuori variabili senza introduzione, l'input non ha nome, non ci sono quantificatori, non si capisce. L'unica cosa che si capisce è che vuoi scrivere $N$ come differenza di quadrati. Che è la stessa identica cosa del metodo di Fermat.

[P_1_6]

"hydro":

Ok ci rinuncio, continua a capirsi molto poco. Spuntano fuori variabili senza introduzione, l'input non ha nome, non ci sono quantificatori, non si capisce. L'unica cosa che si capisce è che vuoi scrivere $N$ come differenza di quadrati. Che è la stessa identica cosa del metodo di Fermat.

Da questa pagina

"P_1_6":[quote="hydro"]Un consiglio: nessuno leggerà mai quel codice. Devi descrivere a parole, e soprattutto in modo chiaro e non ambiguo, qual è l'input, quali sono gli step, e qual è l'output. Ti faccio un esempio. Il metodo di Fermat funziona così: l'input è un intero positivo $N$. L'algoritmo fa la cosa seguente: calcola $\sqrt{N}$, la arrotonda per eccesso trovando un intero $a$ e poi calcola $a^2-N$. Se questo è un quadrato $b^2$, l'algoritmo termina perchè $a-b$ è un fattore non banale di $N$, ed è l'output dell'algoritmo. Altrimenti, si ripete incrementando $a$ di 1, e così via. Ovviamente l'algoritmo termina al più quando $a=N$.

Input n //positive factorizable integer odd


N=n

int i = 1

while(1){
   if ( (N-3) mod (2^(i+1)) !=0 ){
      N=N*((2^i)+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
         break
      }	
   }

i++;

}


Output p & q

Input : un numero dispari fattorizzabile

partiamo da $i =1$

$step1$ : portiamo l'input nella forma $N=4*((2^i)*w)+3$ questo modo:
se $N-3 mod 2^(i+1)$ è diverso da $0$ moltiplichi $N$ per $2^i+1$ e cioè $N=N*(2^i+1)$

Se la nostra $y$ verifica questa disequazione
$4*((2^i)*x+1)^2>=4*((2^i)*x+1)^2-(2*y-1)^2=N>4*((2^i)*(x-1)+1)^2$
significa che $N$ è compreso li in mezzo

$step2$ : ci calcoliamo $x$ in questo modo da $4*((2^i)*a+1)^2=N$
$->$ $a=(sqrt(N)-2)/(2*(2^i))$
$x=($integer$(a))+1$
dove integer$(a)$ significa partei ntera inferiore di $a$

$step3$ : ci calcoliamo da $4*((2^i)*x+1)^2-(2*y-1)^2=N$ la $y$
$y=1/2*(sqrt(4*((2^i)*x+1)^2-N)+1)$

$step4$ : se IsInteger$(y)$ e cioè se $y$ è un intero significa che avremo una qualsiasi fattorizzazione dell'$N$
trasformato fino a questo momento nella fattorizzazione $P*Q$
dove $P=[(2*((2^i)*x+1))-(2*y-1)]$ ; $Q=[(2*((2^i)*x+1))+(2*y-1)]$

$step5$ : Se $P=s*p$ e $Q=t*q$ dove $p$ e $q$ sono i fattori iniziali dell'input $n$
allora $p=MCD(n,P)$ ; $q=n/p$

se lo $step5$ è vero allora $break$ [hai finito] altrimenti incrementa $i$ di una unità e riparti dallo $step1$[/quote]


cosa non capisci?

[P_1_6]

Forse ho sbagliato a tradurre l'idea di base o l'idea è sbagliata o l'assioma da cui parte l'idea è sbagliato.

Assioma:
Ogni numero nella forma
$N=4*((2^b)*w)+3$
si può esprimere in questa forma
$4*((2^b)*x+1)^2-(n/2)^2$

Questo assioma è corretto?


L' idea è :
se $(N-3) mod (2^(i+1))$ è diverso da $0$ si moltiplica $N$ per $2^i+1$ e cioè $N=N*(2^i+1)$

e di cercare di rendere per un opportuno i questa disequazione
$4*((2^i)*x+1)^2>=4*((2^i)*x+1)^2-(2*y-1)^2=N>4*((2^i)*(x-1)+1)^2$

$1<=y<1/2*(2*sqrt((2^i)*((2*2^i)*x-2^i+2))+1)$

lineare


Dove sbaglio ?

[Studente Anonimo]

"P_1_6":
Assioma:
Ogni numero nella forma
$N=4*((2^b)*w)+3$
si può esprimere in questa forma
$4*((2^b)*x+1)^2-(n/2)^2$

1) Non è un assioma.
Rispondi perfavore alle domande
2) Cosa sono \(b,w,x\) ed \(n\) ?
3) Cosa intendi per "esprimere in questa forma"? Intendi che per opportuni \(x\) ed \(n \) si ha
\[ 4\cdot 2^b \cdot w + 3 = 4 \cdot (2^b \cdot x +1)^2 - n^2/4 \]
??

[P_1_6]

2) appartenenti ad N
3) si

[hydro1]

"P_1_6":Forse ho sbagliato a tradurre l'idea di base o l'idea è sbagliata o l'assioma da cui parte l'idea è sbagliato.

Non è che sia sbagliato, è che non leggi i miei post. Vuoi fattorizzare $N$ scrivendolo come differenza di quadrati. L'ha già fatto Fermat 300 anni fa. Funziona, non bisogna introdurre mille variabili a caso come scrivi tu, e ci mette una cosa tipo $O(N^{1/4+\varepsilon})$ step.

[P_1_6]

"P_1_6":Forse ho sbagliato a tradurre l'idea di base o l'idea è sbagliata o l'assioma da cui parte l'idea è sbagliato.

Assioma:
Ogni numero nella forma
$N=4*((2^b)*w)+3$
si può esprimere in questa forma
$4*((2^b)*x+1)^2-(n/2)^2$

Questo assioma è corretto?


L' idea è :
se $(N-3) mod (2^(i+1))$ è diverso da $0$ si moltiplica $N$ per $2^i+1$ e cioè $N=N*(2^i+1)$

e di cercare di rendere per un opportuno i questa disequazione
$4*((2^i)*x+1)^2>=4*((2^i)*x+1)^2-(2*y-1)^2=N>4*((2^i)*(x-1)+1)^2$

$1<=y<1/2*(2*sqrt((2^i)*((2*2^i)*x-2^i+2))+1)$

lineare


Dove sbaglio ?

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$

[gugo82]

"hydro":Vuoi fattorizzare $N$ scrivendolo come differenza di quadrati. L'ha già fatto Fermat 300 anni fa. Funziona, non bisogna introdurre mille variabili a caso come scrivi tu, e ci mette una cosa tipo $O(N^{1/4+\varepsilon})$ step.

Tanto per essere più espliciti: click.

[hydro1]

"gugo82":[quote="hydro"]Vuoi fattorizzare $N$ scrivendolo come differenza di quadrati. L'ha già fatto Fermat 300 anni fa. Funziona, non bisogna introdurre mille variabili a caso come scrivi tu, e ci mette una cosa tipo $O(N^{1/4+\varepsilon})$ step.

Tanto per essere più espliciti: click.[/quote]

Tu dici che questa volta leggerà?

[gugo82]

"hydro":Tu dici che questa volta leggerà?

Cosa costa sperare?

[P_1_6]

"gugo82":[quote="hydro"]Vuoi fattorizzare $N$ scrivendolo come differenza di quadrati. L'ha già fatto Fermat 300 anni fa. Funziona, non bisogna introdurre mille variabili a caso come scrivi tu, e ci mette una cosa tipo $O(N^{1/4+\varepsilon})$ step.

Tanto per essere più espliciti: click.[/quote]

"P_1_6":[quote="hydro"]Un consiglio: nessuno leggerà mai quel codice. Devi descrivere a parole, e soprattutto in modo chiaro e non ambiguo, qual è l'input, quali sono gli step, e qual è l'output. Ti faccio un esempio. Il metodo di Fermat funziona così: l'input è un intero positivo $N$. L'algoritmo fa la cosa seguente: calcola $\sqrt{N}$, la arrotonda per eccesso trovando un intero $a$ e poi calcola $a^2-N$. Se questo è un quadrato $b^2$, l'algoritmo termina perchè $a-b$ è un fattore non banale di $N$, ed è l'output dell'algoritmo. Altrimenti, si ripete incrementando $a$ di 1, e così via. Ovviamente l'algoritmo termina al più quando $a=N$.

Input n //positive factorizable integer odd


N=n

int i = 1

while(1){
   if ( (N-3) mod (2^(i+1)) !=0 ){
      N=N*((2^i)+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
         break
      }	
   }

i++;

}


Output p & q

Input : un numero dispari fattorizzabile

partiamo da $i =1$

$step1$ : portiamo l'input nella forma $N=4*((2^i)*w)+3$ questo modo:
se $N-3 mod 2^(i+1)$ è diverso da $0$ moltiplichi $N$ per $2^i+1$ e cioè $N=N*(2^i+1)$

Se la nostra $y$ verifica questa disequazione
$4*((2^i)*x+1)^2>=4*((2^i)*x+1)^2-(2*y-1)^2=N>4*((2^i)*(x-1)+1)^2$
significa che $N$ è compreso li in mezzo

$step2$ : ci calcoliamo $x$ in questo modo da $4*((2^i)*a+1)^2=N$
$->$ $a=(sqrt(N)-2)/(2*(2^i))$
$x=($integer$(a))+1$
dove integer$(a)$ significa partei ntera inferiore di $a$

$step3$ : ci calcoliamo da $4*((2^i)*x+1)^2-(2*y-1)^2=N$ la $y$
$y=1/2*(sqrt(4*((2^i)*x+1)^2-N)+1)$

$step4$ : se IsInteger$(y)$ e cioè se $y$ è un intero significa che avremo una qualsiasi fattorizzazione dell'$N$
trasformato fino a questo momento nella fattorizzazione $P*Q$
dove $P=[(2*((2^i)*x+1))-(2*y-1)]$ ; $Q=[(2*((2^i)*x+1))+(2*y-1)]$

$step5$ : Se $P=s*p$ e $Q=t*q$ dove $p$ e $q$ sono i fattori iniziali dell'input $n$
allora $p=MCD(n,P)$ ; $q=n/p$

se lo $step5$ è vero allora $break$ [hai finito] altrimenti incrementa $i$ di una unità e riparti dallo $step1$[/quote]

"P_1_6":Forse ho sbagliato a tradurre l'idea di base o l'idea è sbagliata o l'assioma da cui parte l'idea è sbagliato.

Assioma:
Ogni numero nella forma
$N=4*((2^b)*w)+3$
si può esprimere in questa forma
$4*((2^b)*x+1)^2-(n/2)^2$

Questo assioma è corretto?


L' idea è :
se $(N-3) mod (2^(i+1))$ è diverso da $0$ si moltiplica $N$ per $2^i+1$ e cioè $N=N*(2^i+1)$

e di cercare di rendere per un opportuno i questa disequazione
$4*((2^i)*x+1)^2>=4*((2^i)*x+1)^2-(2*y-1)^2=N>4*((2^i)*(x-1)+1)^2$

$1<=y<1/2*(2*sqrt((2^i)*((2*2^i)*x-2^i+2))+1)$

lineare


Dove sbaglio ?

Si basa sulla rappresentazione di un numero come differenza tra due quadrati, ma è o peggiore o migliore o un evoluzione del https://it.wikipedia.org/wiki/Metodo_di ... _di_Fermat

TdC

[P_1_6]

"3m0o":[quote="P_1_6"]
Assioma:
Ogni numero nella forma
$N=4*((2^b)*w)+3$
si può esprimere in questa forma
$4*((2^b)*x+1)^2-(n/2)^2$

1) Non è un assioma.
Rispondi perfavore alle domande
2) Cosa sono \(b,w,x\) ed \(n\) ?
3) Cosa intendi per "esprimere in questa forma"? Intendi che per opportuni \(x\) ed \(n \) si ha
\[ 4\cdot 2^b \cdot w + 3 = 4 \cdot (2^b \cdot x +1)^2 - n^2/4 \]
??[/quote]



grazie
solo ora ho capito il bug nel mio ragionamento cercherò di fixarlo

[P_1_6]

"P_1_6":[quote="3m0o"][quote="P_1_6"]
Assioma:
Ogni numero nella forma
$N=4*((2^b)*w)+3$
si può esprimere in questa forma
$4*((2^b)*x+1)^2-(n/2)^2$

1) Non è un assioma.
Rispondi perfavore alle domande
2) Cosa sono \(b,w,x\) ed \(n\) ?
3) Cosa intendi per "esprimere in questa forma"? Intendi che per opportuni \(x\) ed \(n \) si ha
\[ 4\cdot 2^b \cdot w + 3 = 4 \cdot (2^b \cdot x +1)^2 - n^2/4 \]
??[/quote]



grazie
solo ora ho capito il bug nel mio ragionamento cercherò di fixarlo[/quote]



La prima idea che mi è venuta è:

Si potrebbe portare

questa

$4*((2^b)*w)+3=4*((2^b)*x+1)^2-(n/2)^2$

a questa

$4*((2^b)*w)+3=4*((2^(b+1))*x+1)^2-(n/2)^2$

però c'è il $50%$ delle possibilità che sia vera per i requisiti che ci servono

************* UPDATE

Per far chiarezza
Differenza tra il mio metodo con il nuovo approccio e quello di Fermat su di un numero a me favorevole

MIO

n=155

1° Step

155 -3 mod 4 = 0
->
non si moltiplica
->
si pone 155=4*((2^1)*a+1)^2
->
a=2,61....
->
x=3
->
x=3 ;4*((2^1)*x+1)^2-(2*y-1)^2=155
->
y non è un intero


2° Step

155 -3 mod 8 = 0
->
non si moltiplica
->
si pone 155=4*((2^2)*a+1)^2
->
a=1,30....
->
x=2
->
x=2 ; 4*((2^2)*x+1)^2-(2*y-1)^2=155
->
y=7 che è intero
->
P=2*((2^2)*x+1)-(2*y-1)= 5
Q=2*((2^2)*x+1)+(2*y-1)= 31
->
p=MCD(155 ,5)=5
q=155/5=31

Fine
(2 Step)

Fermat

n=155

1° Step

sqrt(155)=12,...
->
a=13
->
13^2-155 = non quadrato


2° Step

a=14
->
14^2-155 = non quadrato


3° Step

a=15
->
15^2-155 = non quadrato


4° Step

a=16
->
16^2-155 = non quadrato


5° Step

a=17
->
17^2-155 = non quadrato


6° Step

a=18
->
18^2-155 = 169=13^2
->
n=(a-b)*(a+b)

FINE
(6 step)