暗号総崩れ-素数判定が多項式時間で可能
■ このスレッドは過去ログ倉庫に格納されています
0018デフォルトの名無しさん
NGNGfunction MaxPrime(n:Integer):Integer; //n迄の最大の素数
begin
while not isPrime(n) do dec(n);
Result:=n;
end;
function isPrime(n:Integer):boolean;
var r:integer
begin
// ( n is of the from a^b,b>1) って何?
if ( n is of the from a^b,b>1) then
begin Result:=false;exit;end;
r:=2;
while r<n do begin
if gcd(n,r) then begin Result:=false;exit;end;
if isPrime(r) then q:=MaxPrime(r-1);
if (q >= round(4*sqrt(r)*ln(n)) ) then
if ( round(power(n,r-1/q)) mod r) then break;
r:=r+1;
end;
for a:=1 to round(2*sqrt(r)*ln(n)) do
// if( (x-a)^n ≠ (x^n-1) (mod x^r -1 ,n)
if round(power(x-1,n)) mod (power(x,r)-1 ,n) then begin Result:=false;exit;end;
Result:=true;
end;
■ このスレッドは過去ログ倉庫に格納されています