Генерации очень больших простых чисел и их генераторов по модулю N в PHP


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

<?php
set_time_limit(150);                                        #keeps us from reaching max execution so soon. Giant primes take time to find
$bits               = 32;                                   #*32 for how many bits will be in the smaller prime, *64 for how many bits will be in larger prime
$attempts           = 300;                                  #maximum number of trys to find a safe prime
$prime_fail         = true;
for($i = 0; $i < $attempts; $i++){
    $prime          = gmp_random($bits);                    #generate a large random number
    $prime          = gmp_nextprime($prime);                #find the next prime
    $safe_prime     = gmp_add(gmp_mul($prime, 2), 1);           #manufacture the bigger prime candidate so we can make sure it is indeed prime
    if( gmp_prob_prime($safe_prime) == 0 ){
        $prime_fail = true;                                 #set the pimality fail flag
        $safe_prime = NULL;                                 #number was not prime for sure
    }else{
        $prime_fail = false;                                #did not fail probable primality
        break;                                              #no use going on, we found a safe prime
    }
}
if(!$prime_fail){
    #we found the safe prime we were looking for so lets get the generator

    $generator_found            = false;
    $g_upper_limit              = 10;                       #this limits the highest value that g will be selected at, this method will always return the smalles g possible for convinience
    $onemod = gmp_intval(gmp_mod(1, $safe_prime));          #go ahead and calculate 1 % N just to make sure the math of the proceedure is clear.

    for($g = 1; $g <= $g_upper_limit; $g++){
        #For N where N is prime and N=2p+1 where p is prime
        #g is a generator mod N if
        #g^((N-1)/2) != 1 % N and g^((N-1)/p) != 1 % N
        #since N = 2p +1, N-1 = 2p
        #g^(2p/2) != 1 % N and g^(2p/p) != 1 % N
        #g^p != 1 % N and g^2 != 1 % N
        #remember that the = and != are congruent and not congruent
        #that means we need to use modulo exponentiation as congruency measeures if the remainder is the same between two operations
        if(gmp_intval(gmp_powm($g, $prime, $safe_prime)) != $onemod && gmp_intval(gmp_powm($g, 2, $safe_prime)) != $onemod){
            $generator_found    = true;
            break;
        }
    }

    if(!$generator_found){
        #failed to find generator
        die("<h1 style='text-align: center;'>failed to find generator modulo N. Please run setup again.</h1>");
        exit;
    }

    #we have both so lets do the setup
    $setupfile      = "Prime.inc";
    $safe_prime     = gmp_strval($safe_prime, 16);
    $g              = "$g\n";
    @touch($setupfile) or die("<h1 style='text-align: center;'>Unable to create setup file at this time. Please rerun setup.</h1>");
    @$fh = fopen($setupfile, 'x') or die("<h1 style='text-align: center;'>Unable to write to setup file/setup file already exists.(Prime.inc)</h1>");
    @fwrite($fh, $g) or die("<h1 style='text-align: center;'>Unable to write generator to setup file.(Prime.inc)</h1>");
    @fwrite($fh, $safe_prime) or die("<h1 style='text-align: center;'>Unable to write prime to setup file.(Prime.inc)</h1>");
    @fclose($fh);
    echo "<h1 style='text-align: center;'>Prime.inc created and populated sucessfully.</h1>";
}else{
    #we did not find the safe prime we were looking for
    echo "<h1 style='text-align: center;'>Setup Unsuccessful</h1><br />";
    echo "<p style='text-align: center;'>Please Rerun Setup</p>";
}
exit;
?>


Комментарии
3 ответа

1, я бы извлечь пользовательские умирать функции:

function myDie($msg) {
$prefix = "<h1 style='text-align: center;'>";
$postfix = "</h1>";
die($prefix . $postfix . $msg);
}

2, может быть, вы должны заблокировать $setupfile: https://stackoverflow.com/questions/293601/php-and-concurrent-file-access

3, на выход не проходит, так что это лишнее:

if(!$generator_found){
#failed to find generator
die("<h1 style='text-align: center;'>failed to ... Please run setup again.</h1>");
exit; // remove it
}

4, Если у вас есть переменная для имени файла, использовать эту переменную в сообщения об ошибках тоже:

$setupfile      = "Prime.inc";
...
@$fh = fopen($setupfile, 'x') or myDie("Unable to ... (" . $setupfile . ")");

3
ответ дан 5 декабря 2011 в 12:12 Источник Поделиться

Вместо глобального условного оператора гораздо выгоднее использовать граничные условия

Например:

if ($prime_fail){
message_error(PRIME_FAIL);
exit;
}

$generator_found = false;
$g_upper_limit = 10;
$onemod = gmp_intval(gmp_mod(1, $safe_prime));
// ...

3
ответ дан 5 мая 2011 в 09:05 Источник Поделиться

Это не стоит ответа, но, как и все остальное, как было сказано...

Вы можете сделать вещи немного более лаконичным :

$prime_fail         = true;
for($i = 0; $i < $attempts; $i++){
$prime = gmp_random($bits); # generate a large random number
$prime = gmp_nextprime($prime); # find the next prime
$safe_prime = gmp_add(gmp_mul($prime, 2), 1); # manufacture the bigger prime candidate so we can make sure it is indeed prime
if( gmp_prob_prime($safe_prime) == 0 ){
$prime_fail = true; # set the pimality fail flag
$safe_prime = NULL; # number was not prime for sure
}else{
$prime_fail = false; # did not fail probable primality
break; # no use going on, we found a safe prime
}
}
if(!$prime_fail){

По :


  • присвоении $премьер - ценность вы хотите, чтобы иметь

  • избавления от $prime_fail в качестве значения $safe_prime должно быть достаточно.

Результат :

for($i = 0; $i < $attempts; $i++){
$prime = gmp_nextprime(gmp_random($bits)); # find the prime after a large random number
$safe_prime = gmp_add(gmp_mul($prime, 2), 1); # manufacture a bigger prime candidate
if(gmp_prob_prime($safe_prime)){ # make sure it is indeed prime
break; # no use going on, we found a safe prime
}
$safe_prime = NULL; #number was not prime for sure
}
if($safe_prime){

Что касается математики, я бы хотела проверить валидность, но у меня нет опыта в этой области.

2
ответ дан 4 апреля 2013 в 12:04 Источник Поделиться