Domanda sul modulo
Ciao volevo farvi una domanda sul modulo:
{ 192 - { { 2*[(X-1)/6]}^2+{ 2*[(X-1)/6]} }/2}moduloX = 0
{ 55 + { { 2*[(X-1)/6]}^2+{ 2*[(X-1)/6]} }/2}moduloX = 0
Come si trova la X?
Grazie
Scusatemi ma non lo so usare lo strumento per le formule
{ 192 - { { 2*[(X-1)/6]}^2+{ 2*[(X-1)/6]} }/2}moduloX = 0
{ 55 + { { 2*[(X-1)/6]}^2+{ 2*[(X-1)/6]} }/2}moduloX = 0
Come si trova la X?
Grazie
Scusatemi ma non lo so usare lo strumento per le formule
Risposte
Stiamo assumendo $X \equiv 1 \mod 6$? Altrimenti vengono fuori numeri che non sono interi.
Se si, provo a riscrivere quello che hai scritto: prendiamo $X = 6a +1$. Quindi se sto leggendo le parentesi correttamente, quello che hai scritto e' un modo complicato per scrivere
\[
192 - a^2 -a \equiv 0 \mod (6a+1) \\
55 + a^2 + a \equiv 0 \mod (6a-+1).
\]
Se questo e' corretto, avrei in mente di fare come segue, ma non sono sicuro che funzioni.
sommiamo le due equazioni ottenendo $192 + 55 \equiv 0 \mod (6a+1)$, cioe' $247 \equiv 0 \mod (6a-1)$. Per verificare se ha soluzione cerchiamo quindi i divisori di $247$ della forma $6a+1$. Si ha $247 = 13 \cdot 19$, che sono entrambi della forma $6a+1$. Proviamo quindi $a = 2,3,41$ (corrispondenti a $X = 13,19,247$) nelle congruenze e controlliamo se sono verificate. In questo caso mi sembra che ne' $2$ ne' $3$ ne' $41$ funzionino, quindi azzarderei che il sistema di congruenze non ha soluzione. Pero' mi puzza che ci sia qualcosa di sbagliato in questo ragionamento.
Non so se esiste un algoritmo generale "efficiente" per risolvere un problema del genere in generale.
Se si, provo a riscrivere quello che hai scritto: prendiamo $X = 6a +1$. Quindi se sto leggendo le parentesi correttamente, quello che hai scritto e' un modo complicato per scrivere
\[
192 - a^2 -a \equiv 0 \mod (6a+1) \\
55 + a^2 + a \equiv 0 \mod (6a-+1).
\]
Se questo e' corretto, avrei in mente di fare come segue, ma non sono sicuro che funzioni.
sommiamo le due equazioni ottenendo $192 + 55 \equiv 0 \mod (6a+1)$, cioe' $247 \equiv 0 \mod (6a-1)$. Per verificare se ha soluzione cerchiamo quindi i divisori di $247$ della forma $6a+1$. Si ha $247 = 13 \cdot 19$, che sono entrambi della forma $6a+1$. Proviamo quindi $a = 2,3,41$ (corrispondenti a $X = 13,19,247$) nelle congruenze e controlliamo se sono verificate. In questo caso mi sembra che ne' $2$ ne' $3$ ne' $41$ funzionino, quindi azzarderei che il sistema di congruenze non ha soluzione. Pero' mi puzza che ci sia qualcosa di sbagliato in questo ragionamento.
Non so se esiste un algoritmo generale "efficiente" per risolvere un problema del genere in generale.
hai mancato fratto 2
Poi non so se sia una coincidenza ma:
55+(a^2+a)/2
si porta facilmente nella forma X^2+4X+3965
ora (3695)modulo(247)=X e se fosse sempre vero questo allora il tutto è risolto
Poi non so se sia una coincidenza ma:
55+(a^2+a)/2
si porta facilmente nella forma X^2+4X+3965
ora (3695)modulo(247)=X e se fosse sempre vero questo allora il tutto è risolto
Ma hai dei $2$ a moltiplicare.
Prova a riscrivere le due equazioni usando i simboli di dollaro e un pochina di sintassi tex.
Prova a riscrivere le due equazioni usando i simboli di dollaro e un pochina di sintassi tex.
In effetti hai ragione è
55+ 2*(a^2)+ a
quindi diventa
2(X^2)+2X +1976
ora 1976 è divisibile per X e per 247
55+ 2*(a^2)+ a
quindi diventa
2(X^2)+2X +1976
ora 1976 è divisibile per X e per 247
"P_1_6":
Grazie
Scusatemi ma non lo so usare lo strumento per le formule
Prendi la tua
{ 192 - { { 2*[(X-1)/6]}^2+{ 2*[(X-1)/6]} }/2}moduloX = 0
scrivi "\equiv" al posto dell'uguale e scrivi (mod X) alla fine, cioè
{ 192 - { { 2*[(X-1)/6]}^2+{ 2*[(X-1)/6]} }/2} \equiv 0 (mod X)
poi racchiudi il tutto tra simboli di dollaro
${ 192 - { { 2*[(X-1)/6]}^2+{ 2*[(X-1)/6]} }/2} \equiv 0 (mod X)$
Si può migliorare in vari modi, per es. controllando che siano le parentesi giuste, aggiungendo spazi richiudendo e riaprendo il modulo, ... Intanto se è quello che intendi si legge meglio.
La scrittura delle formule è quella standard delle formule in riga, basta solo metterli tra formule e poi c'è il link nel box rosa in alto quando scrivi. Ricordo di aver risposto a molti thread tuoi un annetto fa e forse te l'ho già detto.
Si è giusta ma come si risolve
Ah..un $2$ era dentro la parentesi.
Quindi le due equazioni sono
\[
192−2a^2−a \equiv 0 \mod (6a+1), \\
55+2a^2+a \equiv 0 \mod (6a+1).
\]
Usando lo stesso metodo che ho seguito prima e provando le possibili soluzioni $a = 2,3,41$ si osserva che sono tutte soluzioni del sistema.
Quindi le due equazioni sono
\[
192−2a^2−a \equiv 0 \mod (6a+1), \\
55+2a^2+a \equiv 0 \mod (6a+1).
\]
Usando lo stesso metodo che ho seguito prima e provando le possibili soluzioni $a = 2,3,41$ si osserva che sono tutte soluzioni del sistema.
grazie Pappappero per le tue risposte
ma ti volevo chiedere i passaggi da fare per trovare le soluzioni
ma ti volevo chiedere i passaggi da fare per trovare le soluzioni
Li ho fatti sopra. Sommi le due equazioni e ottieni $247 \equiv 0 \mod (6a+1)$. Quindi cerchi le $a$ tali che $6a +1$ e' un divisore di $247$ e ottieni $a = 2,3,41$ con corrispondenti $6a+1 = 13,19,247$. Una volta ottenuti questi valori di $a$ li sostituisci nelle equazioni iniziali per verificare quali di loro sono effettivamente soluzione; in questo caso io ottengo che tutte e tre sono soluzioni.
grazie Pappappero
ma è proprio quello che voglio risolvere
http://www.albericolepore.org/test-di-p ... ore-in-ok/
ma è proprio quello che voglio risolvere
http://www.albericolepore.org/test-di-p ... ore-in-ok/
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?
Hai qualche fonte in cui si ipotizza (con qualche ragione) che sia un problema polinomiale?
sebbene non sia dimostrato
Una cosa alla volta prima vorrei capire come si risolve quel modulo.
se puoi aiutarmi te ne sarò grato
Cosa non hai capito di ciò che ti ha scritto Pappappero?
Come si risolve conoscendone solo una con l'aritmetica modulare
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$
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$
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:
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?
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?
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
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
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.
Nella parte b) non so di cosa tu stia parlando.
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
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
Non capisco come definisci i new_val, non capisco come definisci $n$, non capisco i conti che fai. Inoltre, se $X = 11$ e $Y = X + 6n$ (come hai scritto sopra), i conti che fai non concordano con questa definizione.
Fare esempi e' utile se gli esempi seguono un procedimento generale. Ma se procedimento generale non lo spieghi, l'esempio si riduce a una serie di moltiplicazioni che per chi legge sono fatte essenzialmente a caso.
Fare esempi e' utile se gli esempi seguono un procedimento generale. Ma se procedimento generale non lo spieghi, l'esempio si riduce a una serie di moltiplicazioni che per chi legge sono fatte essenzialmente a caso.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo