semplice fattorizzazione
semplice fattorizzazione
ecco un esercizietto semplice semplice..
preso un intero n abbastanza grande, tale che n=p*q dove p e q sono numeri primi, determinare p e q.
lista di n:
-35129987
-19755661
-53549227
good luck!
preso un intero n abbastanza grande, tale che n=p*q dove p e q sono numeri primi, determinare p e q.
lista di n:
-35129987
-19755661
-53549227
good luck!
----->[url=http://rubik.forumcommunity.net/]RUBIK'S COMMUNITY![/url]<-----
---->[url=http://varietytribe.forumcommunity.net/]http://varietytribe.forumcommunity.net/[/url]<----
-->[url=http://www.youtube.com/user/giro9414]canale di youtube![/url]<--
---->[url=http://varietytribe.forumcommunity.net/]http://varietytribe.forumcommunity.net/[/url]<----
-->[url=http://www.youtube.com/user/giro9414]canale di youtube![/url]<--
Re: semplice fattorizzazione
Scusa la domanda: posso fattorizzare con qualunque mezzo o non posso usare calcolatori?
Re: semplice fattorizzazione
possibilmente senza calcolatori automatici (esempio programmi al computer)
----->[url=http://rubik.forumcommunity.net/]RUBIK'S COMMUNITY![/url]<-----
---->[url=http://varietytribe.forumcommunity.net/]http://varietytribe.forumcommunity.net/[/url]<----
-->[url=http://www.youtube.com/user/giro9414]canale di youtube![/url]<--
---->[url=http://varietytribe.forumcommunity.net/]http://varietytribe.forumcommunity.net/[/url]<----
-->[url=http://www.youtube.com/user/giro9414]canale di youtube![/url]<--
-
- Messaggi: 17
- Iscritto il: 30 giu 2011, 15:15
- Località: Terni
Re: semplice fattorizzazione
doh! mi hai sgamato...trugruo ha scritto:rsa
beh la fattorizzazione di numeri grandi è uno dei più grandi problemi del momento...
se ti do un numero di 160 cifre, ci metti anni a trovare i suoi divisori col metodo che hai detto te, blue_sky...
forse con questi n di 8 cifre ce la si può fare lo stesso, ma è una rottura...
io avevo in mente un modo nuovo, che però ancora non funziona perfettamente...
----->[url=http://rubik.forumcommunity.net/]RUBIK'S COMMUNITY![/url]<-----
---->[url=http://varietytribe.forumcommunity.net/]http://varietytribe.forumcommunity.net/[/url]<----
-->[url=http://www.youtube.com/user/giro9414]canale di youtube![/url]<--
---->[url=http://varietytribe.forumcommunity.net/]http://varietytribe.forumcommunity.net/[/url]<----
-->[url=http://www.youtube.com/user/giro9414]canale di youtube![/url]<--
-
- Messaggi: 17
- Iscritto il: 30 giu 2011, 15:15
- Località: Terni
Re: semplice fattorizzazione
Non capisco dove sta la matematicità in questo problema.. Bisogna trovare il metodo per trovare i numeri a mano?
Re: semplice fattorizzazione
non lo so, secondo me è risolvibile, ma data la complessità della cosa non assicuro niente..
questo problema era diciamo ironico, ma che potrebbe portare qualcuno ad avere idee interessanti sulla fattorizzazione dei numeri, questione molto importante per la matematica.xXStephXx ha scritto:Non capisco dove sta la matematicità in questo problema.. Bisogna trovare il metodo per trovare i numeri a mano?
----->[url=http://rubik.forumcommunity.net/]RUBIK'S COMMUNITY![/url]<-----
---->[url=http://varietytribe.forumcommunity.net/]http://varietytribe.forumcommunity.net/[/url]<----
-->[url=http://www.youtube.com/user/giro9414]canale di youtube![/url]<--
---->[url=http://varietytribe.forumcommunity.net/]http://varietytribe.forumcommunity.net/[/url]<----
-->[url=http://www.youtube.com/user/giro9414]canale di youtube![/url]<--
Re: semplice fattorizzazione
Ci ho messo un secondo a numero...giro94 ha scritto: forse con questi n di 8 cifre ce la si può fare lo stesso, ma è una rottura...
Comunque quale sarebbe la tua idea??
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
Re: semplice fattorizzazione
in che modo hai fatto?Drago96 ha scritto:Ci ho messo un secondo a numero...giro94 ha scritto: forse con questi n di 8 cifre ce la si può fare lo stesso, ma è una rottura...
Comunque quale sarebbe la tua idea??
io pensavo di partire dal test di disibilità generale, imponendo che sia corretto..
cioè provo a vedere se n è divisibile per p, e impongo che lo sia, così posso ricavare p da n.. il problema è che c'è un "mod p" che non mi convince, ho utilizzato fermat per toglierlo, ma poi non funziona..
----->[url=http://rubik.forumcommunity.net/]RUBIK'S COMMUNITY![/url]<-----
---->[url=http://varietytribe.forumcommunity.net/]http://varietytribe.forumcommunity.net/[/url]<----
-->[url=http://www.youtube.com/user/giro9414]canale di youtube![/url]<--
---->[url=http://varietytribe.forumcommunity.net/]http://varietytribe.forumcommunity.net/[/url]<----
-->[url=http://www.youtube.com/user/giro9414]canale di youtube![/url]<--
Re: semplice fattorizzazione
Credo con un programma
Re: semplice fattorizzazione
Programma...giro94 ha scritto:in che modo hai fatto?Drago96 ha scritto:Ci ho messo un secondo a numero...giro94 ha scritto: forse con questi n di 8 cifre ce la si può fare lo stesso, ma è una rottura...
Comunque quale sarebbe la tua idea??
Testo nascosto:
Ehm... potresti fare un esempio??giro94 ha scritto:io pensavo di partire dal test di disibilità generale, imponendo che sia corretto..
cioè provo a vedere se n è divisibile per p, e impongo che lo sia, così posso ricavare p da n.. il problema è che c'è un "mod p" che non mi convince, ho utilizzato fermat per toglierlo, ma poi non funziona..
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
Re: semplice fattorizzazione
Ci credo, è javascript! E il tuo isInteger è scritto penso nel modo più lento che potevi trovare XD (return s==Math.round(s) ?)Drago96 ha scritto: Programma...Testo nascosto:
EDIT: pro memoria, javascript ha "built-in" i moduli: puoi anche fare n%i==0 invece di prova=n/i isinteger(prova)
(tra un po' ti posto lo stesso programma in C++, pronto a scommettere che a 50 cifre ci arriva senza problemi )
Re: semplice fattorizzazione
Beh, pensavo di farlo molto più semplice, ma poi mi son lasciato trascinare
Codice: Seleziona tutto
#include <iostream>
#include <gmp.h>
using namespace std;
void smallestfactor(mpz_t n,mpz_t* p,mpz_t* f){
if (mpz_probab_prime_p(n,mpz_sizeinbase(n,4)+10)){
mpz_set(*f,n);
return;
}
if(mpz_divisible_ui_p(n,2)){
mpz_set_ui(*f,2);
return;
}
if(mpz_divisible_ui_p(n,3)){
mpz_set_ui(*f,3);
return;
}
if(mpz_divisible_ui_p(n,5)){
mpz_set_ui(*f,5);
return;
}
mpz_t a;
mpz_init(a);
mpz_sqrt(a,n);
for(;mpz_cmp(*p,a)<=0;mpz_add_ui(*p,*p,6)){
if(mpz_divisible_p(n,*p)){
mpz_set(*f,*p);
return;
}
mpz_add_ui(*p,*p,4);
if(mpz_divisible_p(n,*p)){
mpz_set(*f,*p);
mpz_sub_ui(*p,*p,4);
return;
}
mpz_add_ui(*p,*p,2);
if(mpz_divisible_p(n,*p)){
mpz_set(*f,*p);
mpz_sub_ui(*p,*p,6);
return;
}
mpz_add_ui(*p,*p,4);
if(mpz_divisible_p(n,*p)){
mpz_set(*f,*p);
mpz_sub_ui(*p,*p,10);
return;
}
mpz_add_ui(*p,*p,2);
if(mpz_divisible_p(n,*p)){
mpz_set(*f,*p);
mpz_sub_ui(*p,*p,12);
return;
}
mpz_add_ui(*p,*p,4);
if(mpz_divisible_p(n,*p)){
mpz_set(*f,*p);
mpz_sub_ui(*p,*p,16);
return;
}
mpz_add_ui(*p,*p,6);
if(mpz_divisible_p(n,*p)){
mpz_set(*f,*p);
mpz_sub_ui(*p,*p,22);
return;
}
mpz_add_ui(*p,*p,2);
if(mpz_divisible_p(n,*p)){
mpz_set(*f,*p);
mpz_sub_ui(*p,*p,24);
return;
}
}
cout<<"Qualcosa non va!";
return;
}
int main(){
char *nm;
nm=new char[100000000];
mpz_t n;
mpz_t t;
mpz_t p;
cout<<"Inserisci il numero da fattorizzare: ";
cin>>nm;
mpz_init_set_str(n,nm,10);
mpz_init(t);
mpz_init_set_ui(p,7);
while(mpz_cmp_ui(n,1)){
smallestfactor(n,&p,&t);
mpz_divexact(n,n,t);
cout<<t<<" "<<flush;
}
return 0;
}