Gentilmente qualcuno mi direbbe se questo metodo di fattorizzazione è conosciuto ?
gentilmente qualcuno mi direbbe se questo metodo di fattorizzazione è conosciuto ?
sia $N=p*q$
$[a^(N^2)-a] mod (a*N^2)=X$
$gcd(X,N)=p$ or $q$
dove $a$ è un numero naturale pari $> 0$
P.s. non sempre funziona
sia $N=p*q$
$[a^(N^2)-a] mod (a*N^2)=X$
$gcd(X,N)=p$ or $q$
dove $a$ è un numero naturale pari $> 0$
P.s. non sempre funziona
Risposte
Senza perdita di generalità, ipotizziamo che $gcd(X,N)=p$, affinché ciò sia verificato dovrà essere
$(a^(p^2q^2)-a) mod (a*p^2q^2)=kp$
con $k>0$ e $q$ coprimi.
Magari ragionandoci si può ricavare qualcosa di più specifico circa i casi in cui funziona, ma quale sarebbe l'utilità? Saperlo ti tornerebbe utile per qualche applicazione pratica?
$(a^(p^2q^2)-a) mod (a*p^2q^2)=kp$
con $k>0$ e $q$ coprimi.
Magari ragionandoci si può ricavare qualcosa di più specifico circa i casi in cui funziona, ma quale sarebbe l'utilità? Saperlo ti tornerebbe utile per qualche applicazione pratica?
"utente__medio":
Magari ragionandoci si può ricavare qualcosa di più specifico circa i casi in cui funziona, ma quale sarebbe l'utilità? Saperlo ti tornerebbe utile per qualche applicazione pratica?
La fattorizzazione in tempo polinomiale è tuttora un problema aperto
"P_1_6":
La fattorizzazione in tempo polinomiale è tuttora un problema aperto
Tu stesso hai affermato che non funziona sempre, quindi che c'entra la fattorizzazione in generale?
Al massimo si può dire qualcosa di più preciso tra le relazioni che devono sussistere tra $a$, $p$ e $q$ affinché
"utente__medio":
$ (a^(p^2q^2)-a) mod (a*p^2q^2)=kp $
con $ k>0 $ e $ q $ coprimi.
sia vera, ma non vedo in che modo ciò potrebbe essere ritenuto un progresso nel campo della fattorizzazione.
"utente__medio":
[quote="P_1_6"]La fattorizzazione in tempo polinomiale è tuttora un problema aperto
Tu stesso hai affermato che non funziona sempre, quindi che c'entra la fattorizzazione in generale?
Al massimo si può dire qualcosa di più preciso tra le relazioni che devono sussistere tra $a$, $p$ e $q$ affinché
"utente__medio":
$ (a^(p^2q^2)-a) mod (a*p^2q^2)=kp $
con $ k>0 $ e $ q $ coprimi.
sia vera, ma non vedo in che modo ciò potrebbe essere ritenuto un progresso nel campo della fattorizzazione.[/quote]
Non so se funziona sempre [non ho ne dimostrazione ne software (domani lo implemento)]
un certo Eel Ffilibustero in un gruppo facebook mi ha insegnato
"elevazione a potenza in aritmetica modulare mediante quadrati successivi"
che trova in tempi logaritmici questa soluzione
$[a^(N^2)-a] mod (a*N^2)=X$
in particolare $log_2 (N^2)$
quindi il problema è $a$
"P_1_6":
Non so se funziona sempre
Mi pare di no, per esempio per $a=10$, $p=19$ e $q=23$ non funziona.
Quindi come già detto bisogna capire quali relazioni devono sussistere tra $a$, $p$ e $q$ affinché funzioni. Volendo si può provare, ma quale sarebbe l'utilità?
"P_1_6":
un certo Eel Ffilibustero in un gruppo facebook mi ha insegnato
"elevazione a potenza in aritmetica modulare mediante quadrati successivi"
che trova in tempi logaritmici questa soluzione
$ [a^(N^2)-a] mod (a*N^2)=X $
in particolare $ log_2 (N^2) $
quindi il problema è $ a $
Sarà un mio limite, ma non ho capito che intendi...
P.S.
Se ti può interessare ho affrontato una questione simile in un altro post:
https://www.matematicamente.it/forum/vi ... 4#p8682347
"utente__medio":
[quote="P_1_6"]Non so se funziona sempre
Mi pare di no, per esempio per $a=10$, $p=19$ e $q=23$ non funziona.
Quindi come già detto bisogna capire quali relazioni devono sussistere tra $a$, $p$ e $q$ affinché funzioni. Volendo si può provare, ma quale sarebbe l'utilità?
"P_1_6":
un certo Eel Ffilibustero in un gruppo facebook mi ha insegnato
"elevazione a potenza in aritmetica modulare mediante quadrati successivi"
che trova in tempi logaritmici questa soluzione
$ [a^(N^2)-a] mod (a*N^2)=X $
in particolare $ log_2 (N^2) $
quindi il problema è $ a $
Sarà un mio limite, ma non ho capito che intendi...
P.S.
Se ti può interessare ho affrontato una questione simile in un altro post:
https://www.matematicamente.it/forum/vi ... 4#p8682347[/quote]
Diciamo la stessa cosa l'importante è trovare $a$
per $a=8$ il tuo esempio funziona
per quanto riguarda "Sarà un mio limite, ma non ho capito che intendi..."
ti faccio un esempio
Supponiamo di voler fattorizzare $N=9$
$ [a^(N^2)-a] mod (a*N^2)=X ,N=9,gcd(X,N)=p ,a=2 $
dobbiamo calcolare $[[[a^(N^2)] mod (a*N^2)]-a] mod (a*N^2)=X$
quindi dobbiamo calcolare $2^81 mod 162$
scriviamo $81$ in binario
$1010001$
$ 1^2*2^1 mod 162 =2$
$ 2^2*2^0 mod 162 =4$
$ 4*4*2^1 mod 162 =32$
$ 32*32*2^0 mod 162 =52$
$ 52*52*2^0 mod 162 =112$
$112*112*2^0 mod 162 =70$
$ 70*70*2^1 mod 162 =80$
$80-a mod (a*N^2)=X=78$
$gcd(X,N)=gcd(78,9)=p=3$
@P_1_6 perché quoti l'intero messaggio ogni volta?!
In ogni caso, giusto per capire, $N$ è un semiprimo?
In ogni caso, giusto per capire, $N$ è un semiprimo?
"utente__medio":
@P_1_6 perché quoti l'intero messaggio ogni volta?!
In ogni caso, giusto per capire, $N$ è un semiprimo?
Non necessariamente
Ok, quindi mi sembra di capire che il problema che stai cercando di affrontare sia il seguente: dato un numero composto $N$, vuoi sapere per quale numero $a$ (che tu dici debba essere pari) la formula
$gcd{[(a^(N^2)-a) mod (a*N^2)] \ , \ N}$
restituisca un divisore proprio di $N$, giusto?
$gcd{[(a^(N^2)-a) mod (a*N^2)] \ , \ N}$
restituisca un divisore proprio di $N$, giusto?
"utente__medio":
Ok, quindi mi sembra di capire che il problema che stai cercando di affrontare sia il seguente: dato un numero composto $N$, vuoi sapere per quale numero $a$ (che tu dici debba essere pari) la formula
$gcd{[(a^(N^2)-a) mod (a*N^2)] \ , \ N}$
restituisca un divisore proprio di $N$, giusto?
Si
Quindi in definitiva si vuole capire quale relazione deve sussistere tra $a>0$ e un numero composto $N=p*q$ affinché
$(a^(N^2)-a) mod aN^2=kp$
con $k>0$ e $q$ coprimi.
Al momento non ho ottenuto nulla, in ogni caso se può essere utile riporto alcuni passaggi aritmetici che ho fatto.
Utilizzando la proprietà distributiva dell'operazione modulo si ricava
$(a^(N^2)-a) mod aN^2 = [(a^(N^2) mod aN^2) - (a mod aN^2)] mod aN^2 = (a^(N^2) mod aN^2) - a$
Se è sbagliato qualcuno mi corregga, ma mi sembra che in generale se $a mod b=c$ allora $ka mod kb=kc$; in base a ciò si ricava
$(a^(N^2) mod aN^2) - a=a(a^(N^2-1) mod N^2)-a=a[(a^(N^2-1) mod N^2)-1]$
E quindi in definitiva
$(a^(N^2)-a) mod aN^2 = a[(a^(N^2-1) mod N^2)-1]$
$(a^(N^2)-a) mod aN^2=kp$
con $k>0$ e $q$ coprimi.
Al momento non ho ottenuto nulla, in ogni caso se può essere utile riporto alcuni passaggi aritmetici che ho fatto.
Utilizzando la proprietà distributiva dell'operazione modulo si ricava
$(a^(N^2)-a) mod aN^2 = [(a^(N^2) mod aN^2) - (a mod aN^2)] mod aN^2 = (a^(N^2) mod aN^2) - a$
Se è sbagliato qualcuno mi corregga, ma mi sembra che in generale se $a mod b=c$ allora $ka mod kb=kc$; in base a ciò si ricava
$(a^(N^2) mod aN^2) - a=a(a^(N^2-1) mod N^2)-a=a[(a^(N^2-1) mod N^2)-1]$
E quindi in definitiva
$(a^(N^2)-a) mod aN^2 = a[(a^(N^2-1) mod N^2)-1]$
l'ho implementato è funziona anche con a dispari.
non sembrerebbe particolarmente efficiente
sorgente scritto in C con GNU MP Library
https://github.com/Piunosei/factorizati ... 38132533.c
non sembrerebbe particolarmente efficiente
sorgente scritto in C con GNU MP Library
https://github.com/Piunosei/factorizati ... 38132533.c
"P_1_6":
non sembrerebbe particolarmente efficiente
Se non si determinano i casi in cui funziona secondo me non ha nemmeno senso parlare di efficienza.
"utente__medio":
[quote="P_1_6"]non sembrerebbe particolarmente efficiente
Se non si determinano i casi in cui funziona secondo me non ha nemmeno senso parlare di efficienza.[/quote]
In alcuni casi neanche funziona esempio $N=15$
In altri funziona benissimo.
se funziona per $a=p-1 || p || p+1$ questa è vera
"P_1_6":
In alcuni casi neanche funziona esempio $N=15$
Sei sicuro che $N=15$ non funzioni per nessun valore di $a$? Puoi dimostrarlo?
"P_1_6":
In altri funziona benissimo.
Sempre se becchi il valore di $a$ "giusto"...
"P_1_6":
se funziona per $ a=p-1 || p || p+1 $ questa è vera
Non conosco questa simbologia, puoi spiegarmi cosa intendi?
"utente__medio":
[quote="P_1_6"]In alcuni casi neanche funziona esempio $N=15$
Sei sicuro che $N=15$ non funzioni per nessun valore di $a$? Puoi dimostrarlo?
"P_1_6":
In altri funziona benissimo.
Sempre se becchi il valore di $a$ "giusto"...
"P_1_6":
se funziona per $ a=p-1 || p || p+1 $ questa è vera
Non conosco questa simbologia, puoi spiegarmi cosa intendi?[/quote]
Ho notato queste cose:
Le $a$ dipendono esclusivamente dal fattore e non da $N$,
Inoltre se funziona per $a$ funziona anche per $p-a$ e $p+a$ .
Ci potrebbero essere anche $N$ con i fattori grandissimi con un a piccolissimo
1)
quindi nessun $a$ funziona per $N=15$ se non funziona $a=3$ e $a=5$
2)
$a$ sembrerebbe casuale
3)
se funziona allora funziona per $a=p-1$ , $a=p$ , $a=p+1$
Vabbè io ci rinuncio, mi sembra tutto troppo approssimativo...
Le a dipendono esclusivamente dal fattore e non da N,
a sembrerebbe casuale
Complimenti per la coerenza!
In alcuni casi neanche funziona esempio N=15
se è per questo non funziona nemmeno per
1, 2, 3, 5, 15, 35, 255, 1295, ...
a sembrerebbe casuale
Complimenti per la coerenza!
In alcuni casi neanche funziona esempio N=15
se è per questo non funziona nemmeno per
1, 2, 3, 5, 15, 35, 255, 1295, ...
"utente__medio":
Vabbè io ci rinuncio, mi sembra tutto troppo approssimativo...
Devi scusarmi ma sono un principiante e sto studiando da qualche giorno questa formula
questo è più efficiente (sicuramente è da provare)
https://github.com/Piunosei/factorizati ... 38132535.c
https://github.com/Piunosei/factorizati ... 38132535.c
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo