Bonjour tout le monde;
Je suis entrain d'appliquer les calcules sur ma théorie et tout recement j'ai eux une astuce du calcule de reduction de l'incrémentation sur le noyau t.
Mais les fonction divide, multiply restent à desirer car pour les petites valeur tout est OK; mais pour les grands diviseurs je ne comprend rien;
k1 est calculé deux fois et les resultats sont vrai avec les petits diviseurs mais faux pour les grands ( le deuxieme calcule de k1 doit être egal au premier calcule;
voici la trace:
Code:Entrez votre RSA nombre pour chercher ses facteurs premiers: 9 Recherche des facteurs premiers: k1=1 n=5 Delta=0 m1=3 m2=3 f=3*3Code:Entrez votre RSA nombre pour chercher ses facteurs premiers: 21 Recherche des facteurs premiers: k1=2 n=14 Delta=-12 k1=1 n=13 Delta=64 Racine delata=8 r=0 k1=1 k2=3 m1=3 m2=7 f=3*7Le code Java est ici sans inclusion du testMillerRabbin et la fin d'accolade:Code:Entrez votre RSA nombre pour chercher ses facteurs premiers: 22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458199 Recherche des facteurs premiers: k1=2351213810435455999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999 n=22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204551454421116211933026942023089184057337876822823395527472651484517898976079286340504917084977360531888561454285893107248396961653939 Delta=101139615356489487325275888120233025851897881924414793567088436223605932774506701424105707026964684700477879409698433652770906265028757255831539116016754082731518457702604589193160154672690866584368508319355822252430278510127392 Racine delata=318024551499549300000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 r=0 k1=2351213810435456000000000000000000472840417045826876662992265316666859396313585927361052010083372239457402897505421750759545701065 k2=2351213810435456079506137874887325472840417045826876662992265316666859396313585927361052010083372239457402897505421750759545701065 m1=4702427620870912000000000000000000945680834091653753325984530633333718792627171854722104020166744478914805795010843501519091402131 m2=4702427620870912159012275749774650945680834091653753325984530633333718792627171854722104020166744478914805795010843501519091402131 f=4702427620870912000000000000000000945680834091653753325984530633333718792627171854722104020166744478914805795010843501519091402131*4702427620870912159012275749774650945680834091653753325984530633333718792627171854722104020166744478914805795010843501519091402131
Merci pour votre aideCode:package FacteurPremier; import java.util.*; import java.math.BigInteger; import java.util.concurrent.TimeUnit; import java.math.*; public class FacteurPremier { public static void main(String[] args) { //FacteurPremier Lu = new FacteurPremier(); Scanner stdin = new Scanner(System.in); ArrayList U=new ArrayList<BigInteger> (); Object f1=new BigInteger("0"); Object f2=new BigInteger("0"); //BigInteger deux=new BigInteger("2"); System.out.println("Entrez votre RSA nombre pour chercher ses facteurs premiers:"); BigInteger mynum = new BigInteger(stdin.next()); if (MillerRabin(mynum, 50)) System.out.println("Le nombre est premier; Impossible de decomposer"); else { System.out.println("Recherche des facteurs premiers:"); U=Decomposition(mynum); f1=U.get(0); f2=U.get(1); System.out.println("f="+f1+"*"+f2); } stdin.close(); } public static ArrayList<BigInteger> Decomposition(BigInteger f) { ArrayList<BigInteger> V= new ArrayList<BigInteger> (); BigInteger a=new BigInteger("4"); BigInteger c=new BigInteger("0"); BigInteger t=new BigInteger("0"); BigInteger q=new BigInteger("0"); BigInteger k1=new BigInteger("0"); BigInteger k2=new BigInteger("0"); BigInteger n=new BigInteger("0"); BigInteger b=new BigInteger("0"); BigInteger delta=new BigInteger("0"); BigInteger racineDelta=new BigInteger("0"); BigInteger TWO=new BigInteger("2"); BigInteger UN=new BigInteger("1"); BigInteger i1=new BigInteger("0"); BigInteger i2=new BigInteger("0"); BigInteger i3=new BigInteger("0"); BigInteger i4=new BigInteger("0"); BigInteger i5=new BigInteger("0"); BigInteger moin=new BigInteger("-1"); BigInteger deux=new BigInteger("2"); BigInteger m1=new BigInteger("0"); BigInteger m2=new BigInteger("0"); BigInteger deci1=new BigInteger("0"); BigInteger deci2=new BigInteger("0"); BigInteger k3=new BigInteger("0"); //resolution de l'equation du second degré: 4k2-2(n-f)k+n-1=0 qui correspond à la decomposition de f //a=4; b=-2(n-f);c=n-1; delta=b2-4a*c avec racine(delta) dans N et k1,k2 dans N //on commence par recherche du noyau t et calcule n double[] resf=new double[2]; double r,r0; resf[0]=Math.floor(Math.sqrt(f.doubleValue())); resf[1]=resf[0]*resf[0]-f.doubleValue(); r=resf[0];//partie entière de la racine carré r0=resf[1];//partie decimale de -//- BigInteger r1 = BigDecimal.valueOf(r).toBigInteger();//conversion double bigInteger BigInteger r2 = BigDecimal.valueOf(r0).toBigInteger();//conversion double bigInteger // BigInteger r2=new BigInteger("r1"); t=r1; //si q est pair alors t est pair sinon t est impair d'ou le noyau t=t-1 dans if ci-dessous q=f.divide(new BigInteger("2")); if((q.mod(TWO).equals( BigInteger.valueOf(0)))&&(t.mod(TWO).compareTo(new BigInteger("0"))!=0)|| (q.mod(TWO).compareTo(new BigInteger("0"))!=0)&&(t.mod(TWO).equals( BigInteger.valueOf(0)))){ t=t.subtract(new BigInteger("1")); } //au lieu de calculer delta k1 et k2 j'ai trouvé une formule plus rapide que l'incrémentation de n k1=t.divide(new BigInteger("2")); System.out.println("k1="+k1); //k1=t/2 l'incrementation est plus reduite si le noyau t/2 plus proche à k1 //je prefere decomposer ici le calcule de n car je ne maitrise pas assez l'utilisation de la formule ci-dessous i1=i1.add(k1); i2=i1.multiply(i1); i3=i2.multiply(new BigInteger("4")); i4=moin.multiply(i3); i4=moin.multiply(f).add(i4); i5=UN.add(i4); i5=i5.divide(k1.multiply(new BigInteger("2")).add(new BigInteger("1"))); n=f.add(i5); //voici la formule desactivé ici //n=f.add(UN.subtract(f).subtract(new BigInteger("4").multiply(k1).multiply(k1))); System.out.println("n="+n); //n=f+(1-f-4*k1*k1)/(2*k1+1) en Maths b=moin.multiply(new BigInteger("2")).multiply(f.subtract(n)); //b=-2*(f-n) c=n.subtract(UN); //c=n-1 delta=b.multiply(b).subtract(a.multiply(c).multiply(new BigInteger("4"))); //delta=b*b-4*a*c System.out.println("Delta="+delta); //if (delta.compareTo(new BigInteger("0"))<0){ si delta <0 k1 variérra jusqu'à delta superieur ou egal à 0 while(delta.compareTo(new BigInteger("0"))<0){ k1=k1.subtract(new BigInteger("1")); System.out.println("k1="+k1); i1=new BigInteger("0"); i2=new BigInteger("0"); i3=new BigInteger("0"); i4=new BigInteger("0"); i5=new BigInteger("0"); n=new BigInteger("0"); b=new BigInteger("0"); c=new BigInteger("0"); delta=new BigInteger("0"); i1=i1.add(k1); i2=i1.multiply(i1); i3=i2.multiply(new BigInteger("4")); i4=moin.multiply(i3); i4=moin.multiply(f).add(i4); i5=UN.add(i4); i5=i5.divide(k1.multiply(new BigInteger("2")).add(new BigInteger("1"))); n=f.add(i5); System.out.println("n="+n); b=moin.multiply(new BigInteger("2")).multiply(f.subtract(n)); c=n.subtract(UN); delta=b.multiply(b).subtract(a.multiply(c).multiply(new BigInteger("4"))); System.out.println("Delta="+delta); }; if (delta.equals(BigInteger.valueOf(0))){ k2=k1; //k1 étant calculé on a plus besoin de calculer à nouveau k1 et k2 }else { //on calcul la racine de delta do{ resf[0]=Math.floor(Math.sqrt(delta.doubleValue())); resf[1]=resf[0]*resf[0]-delta.doubleValue(); r=resf[0];//partie entiere r0=resf[1];//partie decimale r1 = BigDecimal.valueOf(r).toBigInteger(); //conversion double BigInteger r2 = BigDecimal.valueOf(r0).toBigInteger();//conversion double BigInteger racineDelta=r1; System.out.println("Racine delata="+racineDelta); System.out.println("r="+r2); while(!r2.equals(BigInteger.valueOf(0))){//si la partie entiere est different de 0 alors racine(delta) n'est pas dans N //k1=k1-1 jusqu'a racine(delta) dans N ou r2=0 k1=k1.subtract(new BigInteger("1")); k3=k1; i1=new BigInteger("0"); i2=new BigInteger("0"); i3=new BigInteger("0"); i4=new BigInteger("0"); i5=new BigInteger("0"); n=new BigInteger("0"); b=new BigInteger("0"); c=new BigInteger("0"); delta=new BigInteger("0"); i1=i1.add(k1); i2=i1.multiply(i1); i3=i2.multiply(new BigInteger("4")); i4=moin.multiply(i3); i4=moin.multiply(f).add(i4); i5=UN.add(i4); i5=i5.divide(k1.multiply(new BigInteger("2")).add(new BigInteger("1"))); n=f.add(i5); b=moin.multiply(new BigInteger("2")).multiply(f.subtract(n)); c=n.subtract(UN); delta=b.multiply(b).subtract(a.multiply(c).multiply(new BigInteger("4"))); resf[0]=Math.floor(Math.sqrt(delta.doubleValue())); resf[1]=resf[0]*resf[0]-delta.doubleValue(); r=resf[0]; r0=resf[1]; r1 = BigDecimal.valueOf(r).toBigInteger(); r2 = BigDecimal.valueOf(r0).toBigInteger(); racineDelta=r1; System.out.println("Racine delata="+racineDelta); }; k1=moin.multiply(b).add(moin.multiply(racineDelta)).divide(a.multiply(new BigInteger("2"))); //partie decimale de k1 deci1=moin.multiply(b).add(moin.multiply(racineDelta)).mod(a.multiply(new BigInteger("2"))); k2=moin.multiply(b).add(racineDelta).divide(a.multiply(new BigInteger("2"))); //partie decimal de k2 deci2=moin.multiply(b).add(racineDelta).mod(a.multiply(new BigInteger("2"))); System.out.println("k1="+k1); System.out.println("k2="+k2); //System.out.println("deci1="+deci1); //System.out.println("deci2="+deci2); //si k1 ou k2 n'est pas dans N if(!deci1.equals(BigInteger.valueOf(0))|| !deci2.equals(BigInteger.valueOf(0))){ k1=k3; k1=k1.subtract(new BigInteger("1")); i1=new BigInteger("0"); i2=new BigInteger("0"); i3=new BigInteger("0"); i4=new BigInteger("0"); i5=new BigInteger("0"); n=new BigInteger("0"); b=new BigInteger("0"); c=new BigInteger("0"); delta=new BigInteger("0"); i1=i1.add(k1); i2=i1.multiply(i1); i3=i2.multiply(new BigInteger("4")); i4=moin.multiply(i3); i4=moin.multiply(f).add(i4); i5=UN.add(i4); i5=i5.divide(k1.multiply(new BigInteger("2")).add(new BigInteger("1"))); n=f.add(i5); b=moin.multiply(new BigInteger("2")).multiply(f.subtract(n)); c=n.subtract(UN); delta=b.multiply(b).subtract(a.multiply(c).multiply(new BigInteger("4"))); } }while(!deci1.equals(BigInteger.valueOf(0))||!deci2.equals(BigInteger.valueOf(0))) ; } m1=deux.multiply(k1).add(new BigInteger("1")); m2=deux.multiply(k2).add(new BigInteger("1")); System.out.println("m1="+m1); System.out.println("m2="+m2); V.add(m1); V.add(m2); return V ; }
-----