java cyrptography BigInteger - Сгенерированное простое q, чтобы найти простое P = 2q + 1, Complete - Теперь, как сгенерировать и подтвердить примитивный корень g?

Question

Теперь, когда я сгенерировал простое P, которое является сильным штрихом, как я мог бы создать примитивный корень g?

Я верю, что создам еще один файл bigInt для g, а затем проверьте, является ли он примитивным корнем.

Поколение легко, и я могу сделать это, как и в поколении Prime p.

Проверка, чтобы убедиться, что это примитивный корень, меня немного озадачило. Мне нужно убедиться, что g^q, равное g^((p-1)/2), не соответствует 1 mod p. Есть ли функция BigInteger, чтобы справиться с этим?

Википедия имеет теорию эйлера как это. Но я не уверен, что такое мой а, а это мой n. Я могу использовать^phi (n) для этого форума, правильно?

public void getKey() { 
debug("Getting key (seed) from user"); 

BigInteger primeP; 
BigInteger primeQ; 
int bitLength = 512; 
Random rnd = new Random(); 
boolean boolPrimeP = false; 
boolean boolPrimeQ = false; 
int iteration= 0; 

while (boolPrimeQ == false || boolPrimeP == false){ 
    iteration++; 
    primeQ = BigInteger.probablePrime(bitLength, rnd); 
    boolPrimeQ = primeQ.isProbablePrime(3); 
    if (boolPrimeQ==true){ 
     primeP = primeQ.multiply(BigInteger.valueOf(2)); 
     primeP = primeP.add(BigInteger.valueOf(1)); 
     boolPrimeP = primeP.isProbablePrime(3); 
     if (boolPrimeP==true){ 
      break; 
     } 
    } 
} 

Answer 1

вы хотите создать сильный премьер, или реализовать алгоритм проверки простоты ли? Наглядный P силен, если его ближе к следующему премьер д, чем наибольший простой р меньше P. Математически это означает:

P> (p + q)/2; здесь p является ближайшим меньшим, а q - самым близким терном, чем P.

У BigInteger есть метод nextProbablePrime. Когда генерируются простой р, генерировать следующий P, а затем следующий д, а затем проверить, если P> (р + д)/2

Здесь вы пытаетесь произвести простой P такие, что P = 2 * д - 1, это не сильный премьер, см: https://en.wikipedia.org/wiki/Strong_prime

есть функция BigInteger, чтобы справиться с этим?

Что вы подразумеваете под "этим"? BigInt проверяет примитивность и генерирует простоту, также может вычислять по модулю или другие арифметические операции.

Но я не уверен, что моя а и это мой п

Ваш п тот случай, число P, вы проверяете для простоты. a - это примитивный корень, используемый для проверки, если P является простым.

Как я могу создать примитивный корень g?

Случайным :)

алгоритм Смотрите также Рабина-Миллера. https://rosettacode.org/wiki/Miller%E2%80%93Rabin_primality_test

Answer 2

Нахождение примитивных корней по модулю р трудно, особенно если р очень велико. Я не уверен, есть ли в каждой java-библиотеке встроенная функция GetPrimitive(), но, следуя нижеприведенному методу, это лучшее, что я встречал (это общий алгоритм, описанный на wikipedia).

Вам необходимо будет создать свою собственную функцию для быстрого экспонирования мод p. Это, как правило, очень легкие задачи рекурсии. Ниже псевдокод, который поможет вам начать:

Function FastExpModP(x as int, n as int, p as int) { 
    if (n == 0) { 
     return(1); 
    } else if (n == 1) { 
     return(x); 
    } else if (n mod 2==0) { 
     return(FastExpModP(x^2 mod p, n/2, p)); 
    } else { 
     return(x * FastExpModP(x^2 mod p, (n-1)/2, p)) mod p); 
    } 
} 

Далее вы должны найти все простые числа, которые делят р - 1 (Не обязательно разложение на простые множители), так как phi(p) = p - 1. Предположим, что простые множители р - 1 являются следующие: р , р ..., р _к (есть несколько опубликованы легко понять алгоритмы для выполнения этой задачи уже, поэтому я оставлю это без запроса).

Теперь все, что требуется, чтобы проверить модульную экспоненциацию Mod р каждого элемента (я обычно начинаю с номером 2) по всем показателям вида

( р - 1)/ р _я, для всех 1 < = я < = к

пока не найдете результат, не равный единице для всех показателей. Ниже псевдокод для выполнения этой задачи:

Function GetPrimitive(p as int, pfacs[] as int) { 
    m = p - 1 
    for (int i = 2; i <= m; ++i) { 
     for (int q = 1; q <= pfacs.length; ++q) { 
      test = FastExpModP(i, m/pfacs[q], p) 
      if (test==1) { 
       break; 
      } 
     } 
     if (test > 1) { 
      return(i); 
     } 
    } 
} 

Например, возьмем простое число P = 28764457.Теперь, м = р - 1 и простые множители м являются:

2, 3, 7, 131, и 1307

и м делится на каждый из приведенных выше простых чисел дает:

14382228, 9588152, 4109208, 219576 и 22008

Теперь мы будем перебирать от 2, проверка модульного возведения в степень Mod р, чтобы увидеть, если результат для каждого показателя равен 1. Мы останавливаемся, когда мы находим такое число, что модульное возведение мод р для каждого показателя не равен 1.

For 2 we have: 
    2^14382228 = 1 mod p ==>> stop... try 3 

For 3 we have: 
    3^14382228 = 1 mod p ==>> stop... try 4 

For 4 we have (same as 2 since 4 = 2^2): 
    4^14382228 = 1 mod p ==>> stop... try 5 

For 5 we have: 
    5^14382228 = 28764456 mod p, 5^9588152 = 13076987 mod p, 5^4109208 = 1 mod p ==>> stop... try 6 

For 6 we have: 
    6^14382228 = 1 mod p ==>> stop... try 7 

For 7 we have: 
    7^14382228 = 1 mod p ==>> stop... try 8 

For 8 we have (same as 2 since 8 = 2^3): 
    8^14382228 = 1 mod p ==>> stop... try 9 

For 9 we have (same as 3 since 9 = 3^2): 
    9^14382228 = 1 mod p ==>> stop... try 10 

For 10 we have: 
    10^14382228 = 28764456 mod p, 10^9588152 = 15687469 mod p, 10^4109208 = 23392715 mod p 
    10^219576 = 17852870 mod p, 10^22008 = 5014623 mod p ==>> winner!!! 

Таким образом, вызов функции GetPrimitive(28764457, {2, 3, 7, 131, 1307}) вернет 10 как наименьший примитивный корень мод р.

Для получения более математического фона на эту тему, ознакомьтесь с этим mathematics exchange question.