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

[hydro]

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\).

[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]

[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$.

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$

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

[P_1_6]

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]

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

Codice:

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 ?

[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$.

[P_1_6]

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

Codice:

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$

[hydro]

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]

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

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

Codice:

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$

cosa non capisci?