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)
  41.                 temp.add(A.get(index));
  42.                 temp.add(BigInteger.valueOf(1));
  43.                 Xlist.add(temp);
  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
  61.                 temp.add(BigInteger.valueOf(0));
  62.                 Xlist.add(temp);
  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>();
  74.             temp.add(n);
  75.             temp.add(BigInteger.valueOf(1));               
  76.             Xlist.add(temp);
  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()){
  107.             lowPrimes.add(scan.nextBigInteger());
  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){
  137.                 //F.add(tempPrime);
  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()){
  154.             F.add(tempPrime);
  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());
  350.                     temp.add(tempElement);
  351.                    
  352.                 }
  353.                 solution.add(temp);
  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. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top