<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
"http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv=Content-Type content="text/html; charset=utf8">
<title>/usr/web/sources/contrib/aiju/miller.c - Plan 9 from Bell Labs</title>
<!-- THIS FILE IS AUTOMATICALLY GENERATED. -->
<!-- EDIT sources.tr INSTEAD. -->
</meta>
</head>
<body>
<p style="margin-top: 0; margin-bottom: 0.17in"></p>
<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: center;">
<span style="font-size: 10pt"><a href="/plan9/">Plan 9 from Bell Labs</a>’s /usr/web/sources/contrib/aiju/miller.c</span></p>
<p style="margin-top: 0; margin-bottom: 0.17in"></p>
<p style="margin-top: 0; margin-bottom: 0.17in"></p>
<center><font size=-1>
Copyright © 2009 Alcatel-Lucent.<br />
Distributed under the
<a href="/plan9/license.html">Lucent Public License version 1.02</a>.
<br />
<a href="/plan9/download.html">Download the Plan 9 distribution.</a>
</font>
</center>
<p style="margin-top: 0; margin-bottom: 0.17in"></p>
<table width="100%" cellspacing=0 border=0><tr><td align="center">
<table cellspacing=0 cellpadding=5 bgcolor="#eeeeff"><tr><td align="left">
<pre>
<!-- END HEADER -->
#include <u.h>
#include <libc.h>
u64int mulmod(u64int a, u64int b, u64int p) {
u64int r = 0;
while(b) {
if(b & 1) r = (r + a) % p;
a = (a << 1) % p;
b >>= 1;
}
return r;
}
u64int modpot(u64int a, u64int b, u64int p) {
u64int f = 1;
while(b) {
if(b & 1) f = mulmod(f, a, p);
a = mulmod(a, a, p);
b >>= 1;
}
return f;
}
int miller(u64int n, u64int a) {
u64int s = 0, t = n - 1, j = 0;
while(!(t & 1)) {
t >>= 1;
s++;
}
u64int x = modpot(a, t, n);
if(x == 1) return 1;
while(1) {
if(x+1 == n) return 1;
x = mulmod(x, x, n);
j++;
if((j > s) || (x == 1)) return 0;
}
}
int main(int argc, char** argv) {
srand(time(0));
int i;
for(i=0;i<1000;i++) {
u64int n = ((u64int) rand() << 32) | rand(), a;
u64int topbound = ceil(4 * log(log(n)));
int p = 1;
for(a=1;a<=topbound;a++) {
p = miller(n, a);
if(!p) break;
}
// if(p) print("%lld\n", n);
}
return 0;
}
<!-- BEGIN TAIL -->
</pre>
</td></tr></table>
</td></tr></table>
<p style="margin-top: 0; margin-bottom: 0.17in"></p>
<p style="line-height: 1.2em; margin-left: 1.00in; text-indent: 0.00in; margin-right: 1.00in; margin-top: 0; margin-bottom: 0; text-align: center;">
<span style="font-size: 10pt"></span></p>
<p style="margin-top: 0; margin-bottom: 0.50in"></p>
<p style="margin-top: 0; margin-bottom: 0.33in"></p>
<center><table border="0"><tr>
<td valign="middle"><a href="http://www.alcatel-lucent.com/"><img border="0" src="/plan9/img/logo_ft.gif" alt="Bell Labs" />
</a></td>
<td valign="middle"><a href="http://www.opensource.org"><img border="0" alt="OSI certified" src="/plan9/img/osi-certified-60x50.gif" />
</a></td>
<td><img style="padding-right: 45px;" alt="Powered by Plan 9" src="/plan9/img/power36.gif" />
</td>
</tr></table></center>
<p style="margin-top: 0; margin-bottom: 0.17in"></p>
<center>
<span style="font-size: 10pt">(<a href="/plan9/">Return to Plan 9 Home Page</a>)</span>
</center>
<p style="margin-top: 0; margin-bottom: 0.17in"></p>
<center><font size=-1>
<span style="font-size: 10pt"><a href="http://www.lucent.com/copyright.html">Copyright</a></span>
<span style="font-size: 10pt">© 2009 Alcatel-Lucent.</span>
<span style="font-size: 10pt">All Rights Reserved.</span>
<br />
<span style="font-size: 10pt">Comments to</span>
<span style="font-size: 10pt"><a href="mailto:webmaster@plan9.bell-labs.com">webmaster@plan9.bell-labs.com</a>.</span>
</font></center>
</body>
</html>