Aiuto su Teoria Dei Numeri

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

[3m0o]

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

[hydro]

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]

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]

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.

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

Tu dici che questa volta leggerà?

[gugo82]

Tu dici che questa volta leggerà?

Cosa costa sperare?

[P_1_6]

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.

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$

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]

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 \]
??

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