File: composite.5c

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 (29 lines) | stat: -rw-r--r-- 656 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
 
/* Miller-Rabin test from Corwin/Rivest/Leiserson */
int function witnessexp(int b, int e, int m) {
  if (e == 0)
    return -1;
  if (e == 1)
    return b % m;
  int res = witnessexp(b, e // 2, m);
  if (res == -1)
    return res;
  int 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.) */
public int function composite(int n) {
  for (int j = 0; j < n - 1; j++) {
    if (witnessexp(j + 1, n - 1, n) != 1)
      return j + 1;
  }
  return 0;
}

composite(39157)