semplice fattorizzazione

[giro94]

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!

[xXStephXx]

Scusa la domanda: posso fattorizzare con qualunque mezzo o non posso usare calcolatori?

[giro94]

possibilmente senza calcolatori automatici (esempio programmi al computer)

[Blue Sky_1993]

.

[trugruo]

rsa

[giro94]

rsa

doh! mi hai sgamato...

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...

[Blue Sky_1993]

.

[xXStephXx]

Non capisco dove sta la matematicità in questo problema.. Bisogna trovare il metodo per trovare i numeri a mano?

[giro94]

non lo so, secondo me è risolvibile, ma data la complessità della cosa non assicuro niente..

Non capisco dove sta la matematicità in questo problema.. Bisogna trovare il metodo per trovare i numeri a mano?

questo problema era diciamo ironico, ma che potrebbe portare qualcuno ad avere idee interessanti sulla fattorizzazione dei numeri, questione molto importante per la matematica.

[Drago96]

forse con questi n di 8 cifre ce la si può fare lo stesso, ma è una rottura...

Ci ho messo un secondo a numero...

Comunque quale sarebbe la tua idea??

[giro94]

forse con questi n di 8 cifre ce la si può fare lo stesso, ma è una rottura...

Ci ho messo un secondo a numero...

Comunque quale sarebbe la tua idea??

in che modo hai fatto?

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..

[xXStephXx]

Credo con un programma

[Drago96]

forse con questi n di 8 cifre ce la si può fare lo stesso, ma è una rottura...

Ci ho messo un secondo a numero...

Comunque quale sarebbe la tua idea??

in che modo hai fatto?

Programma...

Testo nascosto:

Codice: Seleziona tutto

<script type="text/javascript">
function isInteger(s) {
  return (s.toString().search(/^-?[0-9]+$/) == 0);
}
function div_primi(num) {
n=parseInt(num);
rad1=Math.sqrt(n);
rad=Math.round(rad1);
for (i=2;i<=rad;i++) {
prova=n/i;
if (isInteger(prova)) {
div1=prova;
div2=i;
break;
};
}
document.write(div1+" "+div2);
}
</script>

Sennò usiamo WolframAlpha! 5 secondi per 50 cifre! (il mio computer si impalla se do al mio programmino numeri simili... )

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..

Ehm... potresti fare un esempio??

[Veluca]

Programma...

Testo nascosto:

Codice: Seleziona tutto

<script type="text/javascript">
function isInteger(s) {
  return (s.toString().search(/^-?[0-9]+$/) == 0);
}
function div_primi(num) {
n=parseInt(num);
rad1=Math.sqrt(n);
rad=Math.round(rad1);
for (i=2;i<=rad;i++) {
prova=n/i;
if (isInteger(prova)) {
div1=prova;
div2=i;
break;
};
}
document.write(div1+" "+div2);
}
</script>

Ci credo, è javascript! E il tuo isInteger è scritto penso nel modo più lento che potevi trovare XD (return s==Math.round(s) ?)
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 )

[Veluca]

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;
}