fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /**
  8.  * Created by Игорь on 25.10.2015.
  9.  */
  10. import  java.util.Random;
  11. public class Main {
  12.     public static void main(String[] args){
  13.         //System.out.println(isPrimeAccordingToMillerRabin(19, 5));
  14.         generatePossiblePrimeWithLength(20);
  15.     }
  16.  
  17.  
  18.     public static int gcd(int a, int b) {
  19.         if (b == 0)
  20.             return Math.abs(a);
  21.         return gcd(b, a % b);
  22.     }
  23.  
  24.     /* Символ якоби
  25.     1 (проверка взаимной простоты). Если НОД (a, b)≠1, выход из алгоритма с ответом 0.
  26.  
  27. 2 (инициализация). r:=1
  28.  
  29. 3 (переход к положительным числам).
  30.  Если a<0 то
  31.   a:=-a
  32.   Если b mod 4 = 3 то r:=-r
  33.  Конец если
  34.  
  35. 4 (избавление от чётности). t:=0
  36.  Цикл ПОКА a – чётное
  37.   t:=t+1
  38.   a:=a/2
  39.  Конец цикла
  40.  Если t – нечётное, то
  41.   Если b mod 8 = 3 или 5, то r:=-r.
  42.  Конец если
  43.  
  44. 5 (квадратичный закон взаимности). Если a mod 4 = b mod 4 = 3, то r:=-r.
  45.   c:=a; a:=b mod c; b:=c.
  46.  
  47. 6 (выход из алгоритма?). Если a≠0, то идти на шаг 4, иначе выйти из алгоритма с ответом r.
  48.      */
  49.     public static int jacobySign(int a, int b) // a - целое, b - натуральное > 1, нечетное
  50.     {
  51.         if (gcd (a, b) != 1){
  52.             return 0;
  53.         }
  54.  
  55.         int r = 1;
  56.  
  57.         if (a < 0){
  58.             a = -a;
  59.  
  60.             if (b % 4 == 3){
  61.                 r = -r;
  62.             }
  63.         }
  64.  
  65.         while (a != 0)
  66.         {
  67.             int t = 0;
  68.  
  69.             while (a % 2 == 0){
  70.                 t++;
  71.                 a /= 2;
  72.             }
  73.  
  74.             if (t % 2 != 0)
  75.             {
  76.                 int mod = b % 8;
  77.  
  78.                 if (mod == 3 || mod == 5)
  79.                 {
  80.                     r = -r;
  81.                 }
  82.             }
  83.  
  84.             int modA = a % 4;
  85.  
  86.             if ((modA == b % 4) && modA  == 3) {
  87.                 r = -r;
  88.             }
  89.             int c = a;
  90.             a = b % c;
  91.             b = c;
  92.         }
  93.  
  94.         return r;
  95.     }
  96.  
  97.  
  98.     public static int randomIntInRange(int min, int max){
  99.         Random rand = new Random();
  100.         int randomNum = rand.nextInt((max - min) + 1) + min;
  101.  
  102.         return randomNum;
  103.     }
  104.  
  105.  
  106.     public static int pow(int foundation, int degree, int modeFoundation){
  107.         int answer = 1;
  108.  
  109.         for (int i = 0; i < degree; i++){
  110.             answer *= foundation;
  111.             answer %= modeFoundation;
  112.         }
  113.  
  114.         return  answer;
  115.     }
  116.  
  117.  
  118.     /*
  119.     Алгоритм Соловея — Штрассена [6] параметризуется количеством раундов k.
  120.     В каждом раунде случайным образом выбирается число a < n. Если НОД(a,n) > 1, то выносится решение, что n составное.
  121.     Иначе проверяется справедливость сравнения \textstyle a^{(n-1)/2} \equiv \left( {a\over n} \right) \pmod{n}.
  122.     Если оно не выполняется, то выносится решение, что n — составное. Если это сравнение выполняется, то a является свидетелем простоты числа n.
  123.     Далее выбирается другое случайное a и процедура повторяется.
  124.     После нахождения k свидетелей простоты в k раундах выносится заключение, что n является простым числом с вероятностью  1 - 2^{-k}  .
  125.  
  126.     Вход: n > 2, тестируемое нечётное натуральное число;
  127.       k, параметр, определяющий точность теста.
  128. Выход: составное, означает, что n точно составное;
  129.        вероятно простое, означает, что n вероятно является простым.
  130.  
  131. for i = 1, 2, ..., k:
  132.    a = случайное целое от 2 до n - 1, включительно;
  133.    если НОД(a, n) > 1, тогда:
  134.        вывести, что n — составное, и остановиться.
  135.    если a^{(n-1)/2} \not\equiv \left( {a\over n} \right) \pmod{n}, тогда:
  136.        вывести, что n — составное, и остановиться.
  137.  
  138. вывести, что n —  простое  с вероятностью \textstyle 1 - 2^{-k} , и остановиться.
  139.      */
  140.  
  141.     public static boolean isPrimeAccordingToSoloveiShtrassen(int number, int accuracy){ //number > 2, нечётное натуральное число
  142.         for (int i = 0; i < accuracy; i++){
  143.             int randomInt = randomIntInRange(2, number - 1);
  144.  
  145.             if (gcd(randomInt, number) > 1){
  146.                 return false;
  147.             }
  148.  
  149.             int checkNumberW = pow(randomInt, (number - 1) / 2, number);
  150.             int jacobySignum = (jacobySign(randomInt, number) + number) % number;
  151.  
  152.             if (checkNumberW != jacobySignum){
  153.                 return false;
  154.             }
  155.         }
  156.  
  157.         return true;
  158.     }
  159.  
  160.  
  161.     /*
  162.     Алгоритм Миллера — Рабина параметризуется количеством раундов r. Рекомендуется брать r порядка величины \log_2(m), где m — проверяемое число.
  163.  
  164. Для данного m находятся такие целое число s и целое нечётное число t, что m-1 = 2^s t.
  165. Выбирается случайное число a, 1 < a < m. Если a не является свидетелем простоты числа m, то выдаётся ответ «m — составное», и алгоритм завершается. Иначе, выбирается новое случайное число a и процедура проверки повторяется.
  166. После нахождения r свидетелей простоты, выдаётся ответ «m — вероятно простое», и алгоритм завершается.
  167.  
  168.      Ввод: m > 2, нечётное натуральное число, которое необходимо проверить на простоту;
  169.        r — количество раундов.
  170. Вывод: составное, означает, что m является составным числом;
  171.        вероятно простое, означает, что m с высокой вероятностью является простым числом.
  172. Представить m − 1 в виде 2s·t, где t нечётно, можно сделать последовательным делением m - 1 на 2.
  173. цикл А: повторить r раз:
  174.    Выбрать случайное целое число a в отрезке [2, m − 2]
  175.    x ← at mod m, вычисляется с помощью алгоритма возведения в степень по модулю
  176.    если x = 1 или x = m − 1, то перейти на следующую итерацию цикла А
  177.    цикл B: повторить s − 1 раз
  178.       x ← x2 mod m
  179.       если x = 1, то вернуть составное
  180.       если x = m − 1, то перейти на следующую итерацию цикла A
  181.    вернуть составное
  182. вернуть вероятно простое
  183.      */
  184.  
  185.     // Рекомендуется брать r порядка величины log2(m), где m — проверяемое число. number > 2, нечётное натуральное число
  186.     public static boolean isPrimeAccordingToMillerRabin(int number, int roundCount){
  187.         int numberMinus1 = number - 1;
  188.         int t = numberMinus1;
  189.         int s = 0;
  190.  
  191.         while (t % 2 == 0)
  192.         {
  193.             t /= 2;
  194.             s++;
  195.         }
  196.  
  197.         for (int i = 0; i < roundCount; i++){
  198.             int randomInt = randomIntInRange(2, number - 2);
  199.             int x = pow(randomInt, t, number);
  200.  
  201.             if (x == 1 || x == numberMinus1) continue;
  202.  
  203.             boolean flagToStop = true;
  204.  
  205.             for (int j = 0; j < s - 1; j++){
  206.                 x = pow(x, 2, number);
  207.  
  208.                 if (x == 1){
  209.                     return false;
  210.                 }
  211.  
  212.                 if (x == numberMinus1){
  213.                     flagToStop = false;
  214.                     break;
  215.                 }
  216.             }
  217.  
  218.             if (flagToStop)
  219.             {
  220.                 return false;
  221.             }
  222.         }
  223.  
  224.         return true;
  225.     }
  226.  
  227.     public static boolean isPrime(int n) {
  228.         boolean r = true;
  229.  
  230.         for (int i = 2; i <= (int) Math.sqrt(n); i++) {
  231.             if (n % i == 0) {
  232.                 r = false;
  233.                 break;
  234.             }
  235.         }
  236.         return r;
  237.     }
  238.  
  239.  
  240.     public static void generatePossiblePrimeWithLength(int length) {
  241.         int primeNumber = 2, roundCount = 5;
  242.         boolean f = false;
  243.         Random rnd = new Random();
  244.  
  245.         while(!f) {
  246.             primeNumber = 2 + rnd.nextInt((int) Math.pow(2, length) - 2);
  247.  
  248.             for(int i = 2; i < 7 && isPrime(i); i++){
  249.                 if(primeNumber % i == 0){
  250.                     f = false;
  251.                     break;
  252.                 }
  253.                 else {
  254.                     f = true;
  255.                 }
  256.             }
  257.  
  258.             if(!isPrimeAccordingToMillerRabin(primeNumber, roundCount)){
  259.                 f = false;
  260.             };
  261.         }
  262.  
  263.         System.out.println("Number: " + primeNumber);
  264.     }
  265.  
  266.  
  267.     /*
  268.     Простое число p называется сильно простым, если существуют целые числа r,s,t, удовлетвоярющие следующим условиям:
  269. 1. p+1 имеет большой простой делитель s;
  270. 2. p-1 имеет большой простой делитель r;
  271. 3. r-1 имеет большой простой делитель t.
  272. В этом определении величина делителей зависит от вида атаки, от которой необходимо защититься.
  273. Алгоритм Гордона (Gordon’s algorithm) для генерации сильно простого числа
  274. Выход: Сильно простое число p.
  275. 1. Сгенерировать два больших простых числа s и t одной длины;
  276. 2. Выбрать число Gus39.gif. Найти первое простое число в последовательности 2it+1, где i= Gus39.gif, i=i+1. Обозначить это число r=2it+1;
  277. 3. Вычислить Gus40.gif;
  278. 4. Выбрать целое число Gus42.gif. Найти первое простое число в последовательности Gus41.gif, где j = Gus42.gif, j=j+1. Обозначить это число p=Gus41.gif;
  279. 5. Вернуть (p).
  280.      */
  281.  
  282.     public static void generateStrongPrime() {
  283.         int k = 9;
  284.         int i0 = 1;
  285.         int j0 = 1;
  286.         int s = 0;
  287.         int t = 0;
  288.  
  289.         boolean isp1 = false;
  290.         boolean isp2 = false;
  291.  
  292.         Random rnd = new Random();
  293.  
  294.         while(!isp1) {
  295.             s = (int) Math.pow(2, k - 1) + rnd.nextInt((int) Math.pow(2, k) - (int) Math.pow(2, k - 1));
  296.             isp1 = isPrime(s);
  297.         }
  298.  
  299.         while(!isp2) {
  300.             t = (int) Math.pow(2, k - 1) + rnd.nextInt((int) Math.pow(2, k) - (int) Math.pow(2, k - 1));
  301.             isp2 = isPrime(t);
  302.         }
  303.         int i = i0;
  304.  
  305.         while(!isPrime(2 * i * t + 1)) {
  306.             i++;
  307.         }
  308.         int r = 2 * i * t + 1;
  309.         int p0 =  2 * pow(s, r - 2, r) * s - 1;
  310.         int j = j0;
  311.  
  312.         while(!isPrime(p0 + 2 * j * r * s)) {
  313.             j++;
  314.         }
  315.         int p = p0 + 2 * j * r * s;
  316.  
  317.         System.out.println("Number :" + p);
  318.     }
  319. }
Success #stdin #stdout 0.6s 55736KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Number: 29741
https://ideone.com/e0y8fO
language:
Java (HotSpot 12)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!