Domanda sul modulo

[P_1_6]

grazie Pappappero
ma è proprio quello che voglio risolvere
http://www.albericolepore.org/test-di-p ... ore-in-ok/

[Pappappero]

A quello che capisco leggendo qui, si ritiene - sebbene non sia dimostrato - che la fattorizzazione intera sia un problema $NP$-completo (e' banalmente $NP$, almeno la versione booleana - la parte difficile da dimostrare e' che sia $NP$-hard).

Hai qualche fonte in cui si ipotizza (con qualche ragione) che sia un problema polinomiale?

[P_1_6]

sebbene non sia dimostrato

Una cosa alla volta prima vorrei capire come si risolve quel modulo.
se puoi aiutarmi te ne sarò grato

[vict85]

Cosa non hai capito di ciò che ti ha scritto Pappappero?

[P_1_6]

Come si risolve conoscendone solo una con l'aritmetica modulare

[P_1_6]

Ciao
credo di aver risolto
vi posto l'esempio di $11*29=319$



Ultima versione

$1485-{[(X^2+6X+5)/6]^2+[(X^2+6X+5)/6 ] }/2 - [(319-X^2)/(6X)-1]*{{{[(X^2+12X+5)/6]}^2 + {[(X^2+12X+5)]/6}}/2 -{[(X^2+6X+5)/6]^2+[(X^2+6X+5)/6 ] } /2}-{{[(319-X^2)/(6X)-2]*[(319-X^2)/(6X)-1]}/2}*X^2=0$

[Pappappero]

Sinceramente non ho capito di che stiamo parlando.

Hai postato nel primo messaggio del thread due equazioni congruenziali; io ho pensato fossero da mettere a sistema e ho dato una soluzione.

Quando dici:

Come si risolve conoscendone solo una con l'aritmetica modulare

non ho ben chiaro a cosa ti riferisci. Vuoi prendere una sola delle due equazioni e in qualche modo classificare le sue (a questo punto infinite) soluzioni? Ci ho pensato un pochino, e non so come fare. Forse si riesce a dire qualcosa del tipo "se esiste una soluzione, allora ce ne e' una piu' piccola di un qualche $N$" e poi per trovare la soluzione basta provarle tutte fino a $N$.

L'ultimo conto che hai fatto non capisco cosa sia. A occhio sembra un'equazione in $X$. Ho l'impressione che si possa ridurre a un polinomio dove $X$ non e' $0$. Gli zeri di questo polinomio dovrebbero essere le $X$ soluzioni del sistema di equazioni congruenziali iniziale? Ma da dove viene questa equazione? E cosa viene fuori sviluppandola?

[P_1_6]

Questa equazione serve a fattorizzare in O(1)
http://www.albericolepore.org/test-di-p ... ore-in-ok/

a)Ogni numero $X*Y=RSA$ con $Y$ ed $X$ numeri primi non divisibile per $2$ e $3$ è nella forma $6G+1$ o $6G+5$
I $6G+1$ si scrivono in questo modo
$X^2+n*(X*6)=RSA$
I $6G+5$ si scrivono in questo modo
$X^2+n*(X*6)+2X=RSA$
$X^2+n*(X*6)+4X=RSA$

b)Ora il nostro caso $RSA=6G+1$
La somma da $1$ fino a $G+1$
scala di $X^2$ rispetto ad $n$ fino ad arrivare a
$n=1$(questo lo scelgo io)

Da qui nasce la formula

[Pappappero]

Ricapitolando. Tu hai un numero $RSA = XY$, con $X,Y$ primi entrambi congrui a $1 \mod 6$ oppure entrambi congrui a $-1 \mod 6$. Scopo del gioco e' trovare $X$ (equivalentemente $Y$); supponiamo $X \le Y$ e chiamiamo $n$ l'intero tale che $Y-X = 6n$. Con queste notazioni, mi torna la prima parte del tuo punto a). Nella seconda parte mi sa che prendi una $n$ diversa.

Nella parte b) non so di cosa tu stia parlando.

[P_1_6]

hai ragione dovevo specificare che quella formula è per il caso $X=6h+5$ e $Y=6k+5$.
La $n$ è la stessa
La parte b) te la spiego con un esempio
prendiamo un numero a caso $11=6*1+5$
$n=1$)$11*17=187$
$[(187-1)/6]+1=32$
new_val_1$=(32*33)/2=528$

$n=2$)$11*23=253$
new_val_2$=946$

$n=3$)$11*17=187$
new_val_3$=1485$

$n=4$)$11*23=253$
new_val_4$=2145$

come puoi notare [new_val_i-new_val_(i+1)]-[new_val_i-new_val_(i-1)]=$X^2$
pertanto se vogliamo scomporre $253$ la formula è
$2145-528- 3 * 418-3*121=0$
dove
$418$=[new_val_2-new_val_1]
(il primo)$3=n-1$
(il secondo)$3=[(n-2)*(n-1)]/2$

spero di essere stato chiaro