Anonymous user
Miller–Rabin primality test: Difference between revisions
→{{header|Bc}}: Allow rng to generate large numbers. While here, clean the code by removing extra semicolons.
(Added Java implementation) |
(→{{header|Bc}}: Allow rng to generate large numbers. While here, clean the code by removing extra semicolons.) |
||
Line 210:
}</lang>
=={{header|
Requires a <tt>bc</tt> with long names.
{{works with|GNU bc}}▼
<lang bc>next = 1; # seed of the random generator▼
scale = 0;▼
(A previous version worked with [[GNU bc]].)
define rand()▼
/* Random number from 0 to 32767. */
next = next * 1103515245 + 12345;▼
▲define rand() {
return ((next/65536) % 32768);▼
/* Cheap formula (from POSIX) for random numbers of low quality. */
}
define rangerand(from, to) {
return (from + rand()%(to-from+1));▼
m = to - from + 1
h = length(m) / 2 + 1 /* want h iterations of rand() % 100 */
b = 100 ^ h % m /* want n >= b */
while (1) {
n = 0 /* pick n in range [b, 100 ^ h) */
r = rand()
while (r < 68) { r = rand(); } /* loop if the modulo bias */
n = (n * 100) + (r % 100) /* append 2 digits to n */
if (n >= b) { break; } /* break unless the modulo bias */
}
}
define miller_rabin_test(n, k)▼
▲ auto d, r, a, x, s;
/* n is probably prime? */
if ( n <= 3) { return(1); }▼
▲define miller_rabin_test(n, k) {
if ( (n % 2) == 0) { return(0); }▼
auto d, r, a, x, s
d = n-1;▼
d = n
}
while (k-- > 0) {
a = rangerand(2, n - 2)
x = (a ^ d) % n
if (
for (r = 0; r < s; r++) {
}
if (
}
}
}
return (1)
}
for (i = 1; i < 1000; i++) {
▲for(i=1; i < 1000; i++) {
i
▲ if ( miller_rabin_test(i, 10) == 1 ) {
▲ i
}
}
quit
=={{header|C}}==
| |||