Aiuto su Teoria Dei Numeri

Messaggioda P_1_6 » 26/10/2021, 09:33

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à?
La matematica è solo un pensiero.
P_1_6
Average Member
Average Member
 
Messaggio: 344 di 740
Iscritto il: 25/12/2014, 10:36

Re: Aiuto su Teoria Dei Numeri

Messaggioda hydro » 26/10/2021, 11:32

P_1_6 ha scritto: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 ha scritto:[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$.
hydro
Senior Member
Senior Member
 
Messaggio: 436 di 1456
Iscritto il: 01/10/2005, 18:22
Località: Italy

Re: Aiuto su Teoria Dei Numeri

Messaggioda P_1_6 » 26/10/2021, 11:38

hydro ha scritto:
P_1_6 ha scritto:
P_1_6 ha scritto:[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$
La matematica è solo un pensiero.
P_1_6
Average Member
Average Member
 
Messaggio: 345 di 740
Iscritto il: 25/12/2014, 10:36

Re: Aiuto su Teoria Dei Numeri

Messaggioda hydro » 26/10/2021, 11:46

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?
hydro
Senior Member
Senior Member
 
Messaggio: 437 di 1456
Iscritto il: 01/10/2005, 18:22
Località: Italy

Re: Aiuto su Teoria Dei Numeri

Messaggioda P_1_6 » 26/10/2021, 11:49

hydro ha scritto: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
La matematica è solo un pensiero.
P_1_6
Average Member
Average Member
 
Messaggio: 346 di 740
Iscritto il: 25/12/2014, 10:36

Re: Aiuto su Teoria Dei Numeri

Messaggioda P_1_6 » 27/10/2021, 09:18

hydro ha scritto: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 ?
La matematica è solo un pensiero.
P_1_6
Average Member
Average Member
 
Messaggio: 347 di 740
Iscritto il: 25/12/2014, 10:36

Re: Aiuto su Teoria Dei Numeri

Messaggioda hydro » 27/10/2021, 17:54

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$.
hydro
Senior Member
Senior Member
 
Messaggio: 438 di 1456
Iscritto il: 01/10/2005, 18:22
Località: Italy

Re: Aiuto su Teoria Dei Numeri

Messaggioda P_1_6 » 28/10/2021, 08:15

hydro ha scritto: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$
La matematica è solo un pensiero.
P_1_6
Average Member
Average Member
 
Messaggio: 348 di 740
Iscritto il: 25/12/2014, 10:36

Re: Aiuto su Teoria Dei Numeri

Messaggioda hydro » 28/10/2021, 09:13

P_1_6 ha scritto: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.
hydro
Senior Member
Senior Member
 
Messaggio: 439 di 1456
Iscritto il: 01/10/2005, 18:22
Località: Italy

Re: Aiuto su Teoria Dei Numeri

Messaggioda P_1_6 » 28/10/2021, 09:36

hydro ha scritto:
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 ha scritto:
hydro ha scritto: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?
La matematica è solo un pensiero.
P_1_6
Average Member
Average Member
 
Messaggio: 349 di 740
Iscritto il: 25/12/2014, 10:36

Prossimo

Torna a Algebra, logica, teoria dei numeri e matematica discreta

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite