暗号総崩れ-素数判定が多項式時間で可能
■ このスレッドは過去ログ倉庫に格納されています
0162137
NGNG今から多項式の割り算をやってみる。
// n がa^b で表せるか確認する。b > 1
int check_powAB(int n)
{
for (a=2;a<=sqrt(n);a++) { // 大手抜き。
for (b=2;b<n;b++) {
m = pow(a,b);
if ( m == n ) return 1;
if ( m > n ) break;
}
}
return 0;
}
// rが素数の場合 1を返す 「素数 "列挙" アルゴリズムを極めるスレ」から。
int isPrime(int r)
{
int i,z;
for (i=1; z=++i; ) {
while(i%--z)
;
if ( z == 1 ) return 1;
}
return 0;
}
// r の最大の約数、qを探す
int FindLargestPrime(int r)
{
m = (int)sqrt(r);
for ( ; m==1; m-- ) {
if ( r % m == 0 ) return m;
}
printf("Error\n");
exit(0);
}
■ このスレッドは過去ログ倉庫に格納されています