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
"utente__medio":
E quindi in definitiva
$(a^(N^2)-a) mod aN^2 = a(a^(N^2-1) mod N^2-1)$
Ne sei proprio sicuro? Non è che intendevi qualche cosa tipo
$(a^(N^2)-a) mod a N^2=a (a^(N^2-1)-1) mod N^2$
Ho scoperto forse una cosa:
se $p$ è primo per ogni $n > 1$ si avrà
$[2^((p^n)^2)-2] mod [2*((p^n)^2)]=X$
$gcd(X,p^n)=p$
Non è "se e solo se" poichè ci sono pseudoprimi (Esempio $15$)
se $p$ è primo per ogni $n > 1$ si avrà
$[2^((p^n)^2)-2] mod [2*((p^n)^2)]=X$
$gcd(X,p^n)=p$
Non è "se e solo se" poichè ci sono pseudoprimi (Esempio $15$)
"sivepofo":
[quote="utente__medio"]
E quindi in definitiva
$(a^(N^2)-a) mod aN^2 = a(a^(N^2-1) mod N^2-1)$
Ne sei proprio sicuro? Non è che intendevi qualche cosa tipo
$(a^(N^2)-a) mod a N^2=a (a^(N^2-1)-1) mod N^2$[/quote]
Quale passaggio riportato nel seguente post
https://www.matematicamente.it/forum/vi ... 0#p8683625
non ti convince?
Potrei essere totalmente accecato ma non mi pare una uguaglianza.
I conti della serva per
$a=5$
$n=3$
$(5^(3^2) - 5) mod 5*3^2$
non sono uguali ai conti
$5(5^(3^2 - 1) mod 3^2 - 1)$
I conti della serva per
$a=5$
$n=3$
$(5^(3^2) - 5) mod 5*3^2$
non sono uguali ai conti
$5(5^(3^2 - 1) mod 3^2 - 1)$
"P_1_6":
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
Ciao @Martino
questa implementazione
Dato un numero $M=a^n$ conoscendo solo $M$ trova $a$ ovvero la base di $log_a (M)=n$
con $a$ primo funziona sicuramente,
se $a$ non è primo non funziona in tutti i casi
se $a$ è primo e $n>1$ la soluzione si trova in $log_2 (M^2)$ $+$ il tempo del calcolo del $mcd(X,M)$
dove
$[2^(M^2)-2] mod [2*(M^2)]=X$
che si risolve con
"elevazione a potenza in aritmetica modulare mediante quadrati successivi"
come mi ha insegnato Eel Ffilibustero
quindi
$gcd(X,M)=a$
Che ne pensi ?
"sivepofo":
Potrei essere totalmente accecato ma non mi pare una uguaglianza.
I conti della serva per
$a=5$
$n=3$
$(5^(3^2) - 5) mod 5*3^2$
non sono uguali ai conti
$5(5^(3^2 - 1) mod 3^2 - 1)$
A me sembra che facciano entrambi $30$.
Io l'espressione
$a(a^(N^2-1) mod N^2-1)$
la intendo come
$a[(a^(N^2-1) mod N^2)-1]$
e non come
$a[a^(N^2-1) mod (N^2-1)]$
Per caso nasce da qui il misunderstanding?
Inoltre a questo punto mi sorge un dubbio: abituato all'operatore [inline]%[/inline] del C/C++, ho dato per scontato che anche $mod$ avesse la stessa priorità di moltiplicazione e divisione, è così?
Bravo! Credo proprio che tu abbia centrato il bersaglio.
Io avrei sempre scritto
$a ≡ b (mod m)$
come comanda la Matematica. Invece ho usato x mod y solo per adeguarmi al vostro stile.
In questo ed in tutti gli altri posto che il nostro Woody scrive su decine e decine di forum e pagine fessbucco
non si vede nulla che abbia a che fare con la Matematica.
Gli operatori di un linguaggio di programmazione fanno ognuno come gli pare e necessitano nel caso di parentesi ben piazzate.
Il % del "C" può comportarsi in modo completamente differente dall'operatore in un altro linguaggio.
Io avrei sempre scritto
$a ≡ b (mod m)$
come comanda la Matematica. Invece ho usato x mod y solo per adeguarmi al vostro stile.
In questo ed in tutti gli altri posto che il nostro Woody scrive su decine e decine di forum e pagine fessbucco
non si vede nulla che abbia a che fare con la Matematica.
Gli operatori di un linguaggio di programmazione fanno ognuno come gli pare e necessitano nel caso di parentesi ben piazzate.
Il % del "C" può comportarsi in modo completamente differente dall'operatore in un altro linguaggio.
Sinceramente non so cosa comanda la Matematica, quindi chiedo:
- è corretto utilizzare $mod$ come un operatore e scrivere una cosa del genere: $17 mod 5 = 2$ ?
- in tal caso qual è la priorità di tale operatore? Io, forse sbagliando non so, gli ho attribuito la stessa precedenza di moltiplicazione e divisione, ma se non è così potete dirmelo, in modo che io sappia come regolarmi con le parentesi?
- è corretto utilizzare $mod$ come un operatore e scrivere una cosa del genere: $17 mod 5 = 2$ ?
- in tal caso qual è la priorità di tale operatore? Io, forse sbagliando non so, gli ho attribuito la stessa precedenza di moltiplicazione e divisione, ma se non è così potete dirmelo, in modo che io sappia come regolarmi con le parentesi?
Dite che devo creare una discussione apposita per avere una risposta circa i dubbi sollevati nel mio precedente post?
"utente__medio":
Dite che devo creare una discussione apposita per avere una risposta circa i dubbi sollevati nel mio precedente post?
L'autorevole wolframalpha dice così:
https://www.wolframalpha.com/input?i=7+mod+3+-1%3DX
https://www.wolframalpha.com/input?i=%2 ... %29+-1%3DX
spero di averti tolto i dubbi
"P_1_6":
spero di averti tolto i dubbi
Non del tutto, grazie comunque.
EDIT:
A scanso di equivoci ho aggiornato il mio precedente post aggiungendo delle parentesi.
"utente__medio":
Sinceramente non so cosa comanda la Matematica, quindi chiedo:
- è corretto utilizzare $mod$ come un operatore e scrivere una cosa del genere: $17 mod 5 = 2$ ?
- in tal caso qual è la priorità di tale operatore? Io, forse sbagliando non so, gli ho attribuito la stessa precedenza di moltiplicazione e divisione, ma se non è così potete dirmelo, in modo che io sappia come regolarmi con le parentesi?
Non ho letto la parte precedente della discussione, ma farei le cose in modo standard usando $a \equiv b $ $(\mod c)$, cosicché nessuno possa avere dubbi sul fatto che si stia affermando che il numero $a$ appartenga alla stessa classe di congruenza di $b$ modulo $c$ (in pratica, che se continuiamo a sottrarre $c$ ad $a$ prima o poi otterremo un numero non negativo, tra zero e $c-1$, che è proprio $b \in \{0,1,2,\ldots,c-1}$).
Per converso, mi par di ricordare che sulla OEIS fosse accettata anche una scrittura senza parentesi in cui si considerava "mod $c$" come operatore, ma francamente, come minimo, mi aspetterei di trovare una definizione a monte dell'articolo in cui mi si chiarisca tale convenzione (per capirci, pongo il numero di "tacche" sull'orologio pari a $c$ e ciò che scrivo dopo "mod $c$", senza parentesi, corrisponde alla classe di resto modulo $c$ del numero che scrivo prima del suddetto operatore "mod").
In effetti. Quando ho scritto Matematica mi riferivo a Gauss (del resto se non lui chi altro?)
L'operatore mod non è la congruenza e prendere come riferimento un linguaggio formale per macchine tipo il "C" non ha significato per me.
Dici "C", io dico: quale compilatore, con quale architettura, quando la precisione cala fino a dare i numeri del lotto come risultato?
In oltre come ho scritto ogni linguaggio per macchine fa a modo suo. Dove prende il segno? Come è implementato? Usa la funzione floor?
L'operatore mod non è la congruenza e prendere come riferimento un linguaggio formale per macchine tipo il "C" non ha significato per me.
Dici "C", io dico: quale compilatore, con quale architettura, quando la precisione cala fino a dare i numeri del lotto come risultato?
In oltre come ho scritto ogni linguaggio per macchine fa a modo suo. Dove prende il segno? Come è implementato? Usa la funzione floor?
Per la cronaca, poi ho aperto un topic apposito: https://www.matematicamente.it/forum/vi ... 1&t=240677
Non so cosa intendi con standard, ma mi sembra di capire che nulla vieti di utilizzare $mod$ come operatore binario e non per forza come relazione ternaria, o sbaglio?
Scusa, ma secondo me tutta questa manfrina non ha molto senso... soprattutto se si considera che tutto sarebbe nato dalla mia seguente domanda:
"marcokrt":
Non ho letto la parte precedente della discussione, ma farei le cose in modo standard usando $a≡b (modc)$, cosicché nessuno possa avere dubbi sul fatto che si stia affermando che il numero $a$ appartenga alla stessa classe di congruenza di $b$ modulo $c$ ...
Non so cosa intendi con standard, ma mi sembra di capire che nulla vieti di utilizzare $mod$ come operatore binario e non per forza come relazione ternaria, o sbaglio?
"sivepofo":
In effetti. Quando ho scritto Matematica mi riferivo a Gauss (del resto se non lui chi altro?)
L'operatore mod non è la congruenza e prendere come riferimento un linguaggio formale per macchine tipo il "C" non ha significato per me.
Dici "C", io dico: quale compilatore, con quale architettura, quando la precisione cala fino a dare i numeri del lotto come risultato?
In oltre come ho scritto ogni linguaggio per macchine fa a modo suo. Dove prende il segno? Come è implementato? Usa la funzione floor?
Scusa, ma secondo me tutta questa manfrina non ha molto senso... soprattutto se si considera che tutto sarebbe nato dalla mia seguente domanda:
"utente__medio":
Inoltre a questo punto mi sorge un dubbio: abituato all'operatore [inline]%[/inline] del C/C++, ho dato per scontato che anche $mod$ avesse la stessa priorità di moltiplicazione e divisione, è così?
"P_1_6":
Ho scoperto forse una cosa:
se $p$ è primo per ogni $n > 1$ si avrà
$[2^((p^n)^2)-2] mod [2*((p^n)^2)]=X$
$gcd(X,p^n)=p$
Non è "se e solo se" poichè ci sono pseudoprimi (Esempio $15$)
In generale deve essere per ogni $A$ intero maggiore di $1$ cioè:
se $p$ è primo per ogni $n > 1$ si avrà
$[A^((p^n)^2)-2] mod [A*((p^n)^2)]=X$
$gcd(X,p^n)=p$
Ho scritto un test di non primalità in C con la libreria GNU MP
https://github.com/Piunosei/Lepore_prim ... st_nr_25.c
p.s.
per "non primalità" intendo che se il test dice che non è primo allora non è primo
se non è primo o è pseudo primo (fattorizzabile) o primo
"P_1_6":
[quote="P_1_6"]Ho scoperto forse una cosa:
se $p$ è primo per ogni $n > 1$ si avrà
$[2^((p^n)^2)-2] mod [2*((p^n)^2)]=X$
$gcd(X,p^n)=p$
Non è "se e solo se" poichè ci sono pseudoprimi (Esempio $15$)
In generale deve essere per ogni $A$ intero maggiore di $1$ cioè:
se $p$ è primo per ogni $n > 1$ si avrà
$[A^((p^n)^2)-2] mod [A*((p^n)^2)]=X$
$gcd(X,p^n)=p$
Ho scritto un test di non primalità in C con la libreria GNU MP
https://github.com/Piunosei/Lepore_prim ... st_nr_25.c
p.s.
per "non primalità" intendo che se il test dice che non è primo allora non è primo
se non è primo o è pseudo primo (fattorizzabile) o primo[/quote]
Scusatemi per il refuso
corretto è
$[A^((p^n)^2)-A] mod [A*((p^n)^2)]=X$
"P_1_6":
[quote="P_1_6"]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
Ciao @Martino
questa implementazione
Dato un numero $M=a^n$ conoscendo solo $M$ trova $a$ ovvero la base di $log_a (M)=n$
con $a$ primo funziona sicuramente,
se $a$ non è primo non funziona in tutti i casi
se $a$ è primo e $n>1$ la soluzione si trova in $log_2 (M^2)$ $+$ il tempo del calcolo del $mcd(X,M)$
dove
$[2^(M^2)-2] mod [2*(M^2)]=X$
che si risolve con
"elevazione a potenza in aritmetica modulare mediante quadrati successivi"
come mi ha insegnato Eel Ffilibustero
quindi
$gcd(X,M)=a$
Che ne pensi ?[/quote]
In effetti si dovrebbe risolvere per ogni numero naturale $A >=2$
$[A^(M^2)-A] mod [A*(M^2)]=X$
$gcd(X,M)=a$
e scegliere $a$ minimo
poichè potrebbe capitare che $a^i$ (con $2<=i<=n$) sia un pseudo-primo in $A$
Esempio $a=1093$
$a^2=1093^2=1194649$ è un pseudo-primo per $A=2$
quindi ad esempio per $1093^4$ l'algoritmo ci restituirà $1093^2=1194649$
questa cosa l'ho notata grazie a Perig (utente di mersenneforum.org)
1093 ?!?!
Interessante... se ne conosce solo un altro simile.
Dacci sotto che scopri il terzo
Interessante... se ne conosce solo un altro simile.
Dacci sotto che scopri il terzo
"sivepofo":
1093 ?!?!
Interessante... se ne conosce solo un altro simile.
Dacci sotto che scopri il terzo
si ne ho trovati solo due tali che
$[A^((a^n)^2)-A] mod [A*((a^n)^2)]=X$
$gcd(X,a^n)=a^n$
con $A=2$ ed $n$ da $2$ a $64$
e con $a$ (dispari) da $3$ a $1000001$
$a=1093$ (numero primo)
$a=3511$ (numero primo)
Gentilmente potresti provarci tu ?
NO!
E non perché sono scortese ma perché
1) sul forum del frate, sai quello in mano alle agenzie governative deviate, ti hanno detto di quali numeri si tratta
2) mi rimane ancora un bricciolo di sanità mentale per non impegnarmi in imprese di questo tipo
E non perché sono scortese ma perché
1) sul forum del frate, sai quello in mano alle agenzie governative deviate, ti hanno detto di quali numeri si tratta
2) mi rimane ancora un bricciolo di sanità mentale per non impegnarmi in imprese di questo tipo
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo