File: composite.bc

package info (click to toggle)
nickle 2.77-1
  • links: PTS
  • area: main
  • in suites: jessie, jessie-kfreebsd
  • size: 2,612 kB
  • ctags: 3,746
  • sloc: ansic: 26,986; yacc: 1,873; sh: 954; lex: 884; makefile: 225
file content (31 lines) | stat: -rw-r--r-- 649 bytes parent folder | download | duplicates (12) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
/* Miller-Rabin test from Corwin/Rivest/Leiserson */
define witnessexp(b, e, m) {
  auto res, t;
  if (e == 0)
    return (-1);
  if (e == 1)
    return (b % m);
  res = witnessexp(b, e / 2, m);
  if (res == -1)
    return (res);
  t = (res * res) % m;
  if (t == 1 && res != 1 && res != m - 1)
    return (-1);
  if (e % 2 == 0)
    return (t);
  return ((t * b) % m);
}

/* Note that rather than trying random
   bases, we try *all* bases[*]... */
/* ([*] Don't even think it.) */
define composite(n) {
  auto j;
  for (j = 0; j < n - 1; j++) {
    if (witnessexp(j + 1, n - 1, n) != 1)
      return (j + 1);
  }
  return (0);
}

composite(39157)