• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Nov 19th, 2019 87 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1.
2.
3. import java.math.*;
4. import java.util.Scanner;
5. import java.util.ArrayList;
6. import java.io.PrintWriter;
7. import java.io.File;
8. import java.io.FileNotFoundException;
9.
10.
11.
12. public class Cryptology_task1 {
13.
14.
15.     //Calculate BigInteger square root for number x
16.     public static BigInteger squareRoot(BigInteger x) {
17.           BigInteger right = x, left = BigInteger.ZERO, mid;
18.           while(right.subtract(left).compareTo(BigInteger.ONE) > 0) {
19.                 mid = (right.add(left)).shiftRight(1);
20.                 if(mid.multiply(mid).compareTo(x) > 0)
21.                       right = mid;
22.                 else
23.                       left = mid;
24.           }
25.           return left;
26.     }
27.
28.
29.     // Factorize number version ArrayList 02
30.     // Will return a matrix containing the primefactors (<B) and powers for a number n
31.     public static BigInteger[][] smallFactor(ArrayList<BigInteger> A, BigInteger n){
32.         ArrayList<ArrayList<BigInteger>> Xlist = new ArrayList<ArrayList<BigInteger>>(); //Vector of all primes in A, and their power
33.
34.         BigInteger top = squareRoot(n);    //Upper limit for search
35.         int index = 0;
36.
37.         while (A.get(index).compareTo(top) <= 0){   //While the current prime is smaller than sqrt(n)
38.             if (n.mod(A.get(index)).compareTo(BigInteger.valueOf(0)) == 0){    //If A(index) divides n
39.
40.                 ArrayList<BigInteger> temp = new ArrayList<BigInteger>();      //Create a row in Xlist containing the prime A(index)
44.
45.                 BigInteger exponent = Xlist.get(index).get(1).add(BigInteger.valueOf(1));  //Define the next exponent
46.                 while(n.mod(Xlist.get(index).get(0).pow(exponent.intValue())).compareTo(BigInteger.ZERO) == 0){ //If A^ext also divides n
47.                     Xlist.get(index).set(1, exponent);                          //increase the power
48.                     exponent = exponent.add(BigInteger.valueOf(1));
49.
50.                 }
51.
52.                 n = n.divide(Xlist.get(index).get(0).pow(Xlist.get(index).get(1).intValue()));  //Divide n by prime and it's power
53.                 if(n.compareTo(BigInteger.ONE) == 0){           // Break if all factors have been found
54.                     break;
55.                 }
56.
57.             }
58.             else{  // If not divisor, set this row to 0
59.                 ArrayList<BigInteger> temp = new ArrayList<BigInteger>();
60.                 temp.add(BigInteger.valueOf(1)); // recent change
63.             }
64.             index++;
65.
66.             if (index >= A.size()){ // If i is out of bounds, terminate
67.                 break;
68.             }
69.         }
70.
71.         // If remainder exists, place it last
72.         if (n.compareTo(BigInteger.valueOf(1)) == 1){
73.             ArrayList<BigInteger> temp = new ArrayList<BigInteger>();
77.         }
78.
79.         // Transform to matrix
80.         BigInteger[][] X = new BigInteger[Xlist.size()][2];
81.         for(int k = 0; k < Xlist.size(); k++){
82.             X[k][0] = Xlist.get(k).get(0);
83.             X[k][1] = Xlist.get(k).get(1);
84.         }
85.
86.         return X;
87.     }
88.
89.     //-------------------------------------------------------------------------------------------------------------
90.     //-------------------------------------------------------------------------------------------------------------
91.     public static void main(String[] args) {
92.
93.         long startTime = System.nanoTime();  //Measure elapsed time for the program
94.
95.         // Read primes from file ----------------------------------------------------------------------------------
96.         Scanner scan = null;
97.         try {
98.             scan = new Scanner(new File("prim_2_24.txt"));
99.         } catch(FileNotFoundException e){
100.             System.err.println("The file prim_2_24.txt could not be opened");
101.             System.exit(1);
102.         }
103.
104.         ArrayList<BigInteger> lowPrimes = new ArrayList<BigInteger>();
105.
106.         while(scan.hasNext()){
108.         }
109.
110.         scan.close();
111.
112.
113.
114.         // Quadratic sieve ----------------------------------------------------------------------------------------
115.         // Generate suitable candidates
116.
117.         // Essential parameters
118.         // the number to factorize
119.         //BigInteger N = new BigInteger("323");      // for 323, B = 15 and L = 5 works fine
120.         //BigInteger N = new BigInteger("307561");     // for 307561, B = 50 and L = 20 works fine
121.         //BigInteger N = new BigInteger("31741649");     // for 31741649, B = 50 and L = 20 works fine as well
122.         //BigInteger N = new BigInteger("3205837387");     // for 3205837387, B = 80 and L = 25 works fine
123.         //BigInteger N = new BigInteger("392742364277");     // for 392742364277, not working yet
124.         BigInteger N = new BigInteger("165895369126610396357353");     // for 165895369126610396357353, B =  and L =  works fine
125.
126.         // original way to set parameters
127.         //BigInteger B = new BigInteger("1024");   // Smoothness parameter
128.         //int L = 100;                              // Not really L, but rather L - |F|, i.e the difference between the two
129.         //Boolean readSolution = true;           // Do you want to calculate solution too?
130.
131.             //Initialize
132.             //ArrayList<BigInteger> F = new ArrayList<BigInteger>();  //Factorbase
133.
134.             //BigInteger tempPrime = lowPrimes.get(0);
135.             //int i = 0;
136.             //while(tempPrime.compareTo(B) <= 0){
138.                 //i++;
139.                 //tempPrime = lowPrimes.get(i);
140.             //}
141.
142.
143.         // alternative way to set parameters
144.         BigInteger B = new BigInteger("1024");
145.         //BigInteger B = new BigInteger("128");
146.         int L = 10; // Not really L, but rather L - |F|, i.e the difference between the two
147.         Boolean readSolution = true;
148.
149.         ArrayList<BigInteger> F = new ArrayList<BigInteger>();  //Factorbase
150.
151.         BigInteger tempPrime = lowPrimes.get(0);
152.         int i = 0;
153.         while(i <= B.intValue()){
155.             i++;
156.             tempPrime = lowPrimes.get(i);
157.         }
158.
159.
160.
161.         int width = F.size();
162.         int rlim = width + L;
163.         BigInteger [][] r = new BigInteger [rlim][2];
164.         int [][] M = new int [rlim][width];
165.
166.         // Initiate r & M, by setting to 0
167.         for (int k = 0; k < rlim; k++){
168.             r[k][0] = BigInteger.valueOf(0);
169.             r[k][0] = BigInteger.valueOf(0);
170.             for (int j = 0; j < width; j++){
171.                 M[k][j] = 0;
172.             }
173.         }
174.
175.         i = 0;  // Will now be used as index for found rows
176.         Boolean flag = false;  // Break condition
177.
178.         // Diagnostics data
179.         long test1 = 0;
180.         long test2 = 0;
181.
182.         for (int k = 0; k < B.multiply(BigInteger.valueOf(2)).intValue(); k++){ //Might tweak the limit later
183.
184.             if (flag){ // Exit loop if all the numbers have been generated
185.                 break;
186.             }
187.
188.             for (int j = 0; j < k; j++){ //My preferred way to implement it
189.
190.                 BigInteger rtemp = squareRoot(N.multiply(BigInteger.valueOf(k))).add(BigInteger.valueOf(j));  //generate candidate r
191.                 BigInteger ytemp = rtemp.pow(2).mod(N);          // y = r^2 mod N
192.
193.                 if(ytemp.compareTo(BigInteger.ONE) > 0){  // if ytemp > 1
194.
195.                     BigInteger[][] Y = smallFactor(F,ytemp);  // Factorize ytemp
196.
197.                     int len = Y.length;
198.
199.                     test1++;
200.
201.                     // test whether Y is implemented correctly
202.                     BigInteger testY = BigInteger.valueOf(1);
203.
204.                     for(int a = 0; a < len; a++){
205.                         if(Y[a][0].compareTo(BigInteger.ZERO) != 0){
206.                             testY = testY.multiply(Y[a][0].pow(Y[a][1].intValue()));
207.                         }
208.
209.                     }
210.
211.                     if(testY.compareTo(ytemp) == 0){
212.                         test2++;
213.                     }
214.
215.
216.                     if(Y[len-1][0].compareTo(F.get(F.size() - 1)) <= 0){ // If no bigger prime factor is involved
217.
218.                         // Calculate new row
219.                         int [] Mtemp = new int[width];
220.                         //for(int a = 0; a < len; a++){
221.                         for(int a = 0; a < width; a++){
222.                             if(a < len){
223.                                 Mtemp[a] = Y[a][1].mod(BigInteger.valueOf(2)).intValue();// Place even and odd factors in row i of M
224.                             }else{
225.                                 Mtemp[a] = 0;
226.                             }
227.
228.                         }
229.
230.                         Boolean doub = true;
231.                         int sumrows = 0;
232.
233.                         // Check for duplicate rows
234.                         for(int t = 0; t < i; t++){ //
235.                             sumrows = 0;
236.                             for(int a = 0; a < width; a++){
237.                                 if(M[t][a] - Mtemp[a] != 0){  // If any element in row differs, they are not identical
238.                                     break;
239.                                 }
240.                                 else{
241.                                     sumrows++;
242.                                 }
243.                             }
244.                             if(sumrows == width){  // If all elements in a row are equal, there exists a duplicate, and Mtemp is discarded
245.                                 doub = false;
246.                                 break;
247.                             }
248.                         }
249.
250.
251.                         if (doub){ // If no duplicates, add to vector and matrix
252.
253.
254.                             r[i][0] = rtemp;
255.                             r[i][1] = ytemp;
256.
257.                             for(int a = 0; a < width; a++){
258.                                 M[i][a] = Mtemp[a];
259.                             }
260.
261.
262.
263.                             i++;
264.
265.                             if (i > M.length - 1){  //If we have found all elements we need
266.                                 flag = true;
267.                                 break;
268.                             }
269.                         }
270.                     }
271.                 }
272.             }
273.         }
274.
275.         /*
276.         // Print the result
277.         System.out.println("The generated vector r and y, as well as the matrix M: ");
278.         for(int k = 0; k < rlim; k++){
279.             System.out.printf("%4d...%4d...%4d...", k, r[k][0], r[k][1]);
280.             for(int j = 0; j < width; j++){
281.                 System.out.printf("%4d...", M[k][j]);
282.             }
283.             System.out.println();
284.         }*/
285.
286.         //Print test results
287.         System.out.println("Test1: " + test1 + ", Test2 = " + test2);
288.
289.
290.
291.
292.
293.         // Save result to .txt file
294.         PrintWriter NumberOut = null;
295.
296.         try{
297.             NumberOut = new PrintWriter(new File("matrices.txt"));
298.         } catch (FileNotFoundException e){
299.             System.err.println("The file matrices.txt could not be opened");
300.             System.exit(1);
301.         }
302.
303.         NumberOut.printf("%5d %5d%n", rlim, width);  // M N
304.
305.         for(int k = 0; k < rlim; k++){
306.             for(int j = 0; j < width; j++){
307.                 NumberOut.printf("%1d ", M[k][j]);
308.             }
309.             NumberOut.println();
310.         }
311.
312.
313.         NumberOut.close();
314.
315.         long stopTime = System.nanoTime();
316.         long elapsedTime = (stopTime-startTime)/1000000; // Measure elapsed time in milliseconds
317.         System.out.println("Time to generate Matrix in milliseconds: " + elapsedTime);
318.
319.
320.
321.         //----------------------------------------------------------------------------------------------------------------------
322.         // Down here we read solution from the GaussBin.exe run manually
323.         // Run with command: start "" "GaussBin.exe" matrices.txt matricesOut.txt (Note for self)
324.
325.         if(readSolution){  // If we have solutions from GaussBin.exe
326.
327.             startTime = System.nanoTime();  // Measure time for calculating the solution
328.
329.             // open file
330.             scan = null;
331.             try {
332.                 scan = new Scanner(new File("matricesOut.txt"));
333.             } catch(FileNotFoundException e){
334.                 System.err.println("The file matricesOut.txt could not be opened");
335.                 System.exit(1);
336.             }
337.
338.             BigInteger nSol = new BigInteger(scan.nextLine()); //Number of solutions
339.             ArrayList<ArrayList<BigInteger>> solution = new ArrayList<ArrayList<BigInteger>>();
340.             Scanner scanRow = null;
341.
342.
343.             // Read the matrix from the file
344.             while(scan.hasNextLine()){
345.                 String row = scan.nextLine();
346.                 scanRow = new Scanner(row);
347.                 ArrayList<BigInteger> temp = new ArrayList<BigInteger>();
348.                 while(scanRow.hasNext()){
349.                     BigInteger tempElement = new BigInteger(scanRow.next());
351.
352.                 }
354.                 scanRow.close();
355.             }
356.             scan.close();
357.
358.             // Convert the solutions to a matrix
359.             BigInteger[][] Solutions = new BigInteger[solution.size()][solution.get(0).size()];
360.             for(int k = 0; k < nSol.intValue(); k++){
361.                 for(int j = 0; j < rlim; j++){
362.                     Solutions[k][j] = solution.get(k).get(j);
363.                 }
364.             }
365.
366.
367.             // Use the Solutions to factorize the number N ------------------------------------------------------
368.             i = 0;  //now number for current solution
369.
370.
371.             // Diagnostics data
372.             long passTest0 = 0;
373.             long passTest1 = 0;
374.             long passTest2 = 0;
375.
376.
377.             Boolean Success = false;
378.             BigInteger factor1 = null;
379.             BigInteger factor2 = null;
380.
381.             while(!Success && i < nSol.intValue()){  // Until we find a solution or run out of possible solutions
382.                 BigInteger productX = new BigInteger("1");  // One of the primefactors
383.                 BigInteger productY = new BigInteger("1");  // Another of the primefactors
384.
385.
386.                 /*
387.                 // very basic test
388.                 for(int j = 0; j < rlim; j++){
389.                     if(Solutions[i][j].compareTo(BigInteger.ONE)== 0){  // if number is 1, we multiply with the row
390.
391.                         productX = productX.multiply(r[j][0]);          //multiply with r
392.                         productY = productY.multiply(r[j][1]);          //multiply with y
393.
394.
395.                         // modulo N
396.                         productX = productX.mod(N);
397.                         productY = productY.mod(N);
398.
399.                     }
400.                 }*/
401.
402.
403.
404.                 BigInteger[][] factorY = new BigInteger[width][2];
405.                 for(int k = 0; k < width; k++){
406.                     factorY[k][0] = BigInteger.valueOf(1);
407.                     factorY[k][1] = BigInteger.valueOf(0);
408.                 }
409.
410.
411.                 for(int j = 0; j < rlim; j++){
412.                     if(Solutions[i][j].compareTo(BigInteger.ONE)== 0){  // if number is 1, we multiply with the row
413.
414.                         productX = productX.multiply(r[j][0]);                      //multiply with r
415.                         productY = productY.multiply(r[j][1]);                      //multiply with y
416.
417.                         // lets try another way for productY
418.                         BigInteger[][]Y = smallFactor(F,r[j][1]);
419.                         BigInteger littleProd = BigInteger.valueOf(1);
420.
421.                         for(int k = 0; k < Y.length; k++){
422.                             littleProd = littleProd.multiply(Y[k][0].pow(Y[k][1].intValue()));
423.
424.                             //if(littleProd.compareTo(r[j][1]) == 0){
425.                                 //passTest2++;
426.                             //}
427.
428.
429.                             //productY = productY.multiply(littleProd);  // kept as a reference
430.
431.                             if(factorY[k][0].compareTo(BigInteger.ONE) == 0){
432.                                 factorY[k][0] = Y[k][0];
433.                             }
434.                             factorY[k][1] = factorY[k][1].add(Y[k][1]);
435.                         }
436.
437.                         // modulo N
438.                         productX = productX.mod(N);
439.                         productY = productY.mod(N);
440.                         //passTest0++;
441.                     }
442.
443.                 }
444.
445.
446.                 // Now we try to construct productY from the factors
447.                 BigInteger newproductY = BigInteger.valueOf(1);
448.                 BigInteger bigProductY = BigInteger.valueOf(1);
449.                 for(int k = 0; k < width; k++){
450.
451.                     // first I want to test it;
452.
453.
454.                     bigProductY = bigProductY.multiply(factorY[k][0].pow(factorY[k][1].intValue()));
455.                     bigProductY = bigProductY.mod(N);
456.
457.
458.                     if(factorY[k][1].mod(BigInteger.valueOf(2)).compareTo(BigInteger.ZERO) == 0){
459.                         factorY[k][1] = factorY[k][1].divide(BigInteger.valueOf(2));
460.                     }else{
461.                         System.out.println("Error, not divisible by 2");
462.                     }
463.
464.                     if(factorY[k][0].compareTo(BigInteger.ZERO) != 0){
465.                         newproductY = newproductY.multiply(factorY[k][0].pow(factorY[k][1].intValue()));
466.                         newproductY = newproductY.mod(N);
467.                     }
468.
469.                 }
470.
471.                 /*
472.                 // check if they are equal
473.                 if(((newproductY.pow(2)).mod(N)).compareTo(productY) == 0){
474.     //              System.out.println("Molto bene");
475.                 }*/
476.
477.                 // modulo N
478.                 //productX = productX.mod(N);
479.                 //productY = productY.mod(N);
480.
481.
482.
483.                 i++;
484.                 // Check N, it seems to change
485.                 //if((productX.pow(2)).mod(N).compareTo((productY.pow(2)).mod(N)) == 0){ // see if X^2 mod n = Y^2 mod n
486.                 if((productX.pow(2)).mod(N).compareTo((productY).mod(N)) == 0){ // see if X^2 mod n = Y^2 mod n
487.                 //if((productX.pow(2)).mod(N).compareTo((newproductY.pow(2)).mod(N)) == 0){ // see if X^2 mod n = Y^2 mod n
488.
489.                     //BigInteger sqrtY = squareRoot(productY);
490.
491.                     //if(((sqrtY.pow(2)).mod(N)).compareTo(productY) == 0){
492.                     //if((bigProductY.mod(N)).compareTo(productY) == 0){
493.                     if(((newproductY.pow(2)).mod(N).compareTo(bigProductY.mod(N)) == 0) && bigProductY.mod(N).compareTo(productY) == 0){
494.                         passTest2++;
495.                     }
496.
497.                     passTest1++;
498.                     //passTest2++;
499.
500.                     //factor1 = productX.subtract(productY).abs();
501.                     factor1 = productX.subtract(newproductY).abs();
502.
503.                     //factor1 = productX.
504.                     factor1 = factor1.gcd(N);
505.                     if((factor1.compareTo(BigInteger.ONE) != 0) && (factor1.compareTo(N) != 0)){  // If factor 1 is not 1 or N
506.                         factor2 = N.divide(factor1);   // We have found both factors
507.                         Success = true;
508.
509.                         // Print solutions
510.                         System.out.print(factor1);
511.                         System.out.print(" ");
512.                         System.out.println(factor2);
513.                     }
514.
515.                 }
516.
517.             }
518.
519.             System.out.println("Pass test 0: " + passTest0 + " Pass test 1: " + passTest1 + " Pass test 2: " + passTest2);
520.
521.             stopTime = System.nanoTime();
522.             elapsedTime = (stopTime-startTime)/1000000; // Measure elapsed time in milliseconds
523.
524.             System.out.println("Time to generate primefactors in milliseconds: " + elapsedTime);
525.
526.         }
527.     }
528. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!

Top