Bernoulli numbers modulo p#

AUTHOR:

  • David Harvey (2006-07-26): initial version

  • William Stein (2006-07-28): some touch up.

  • David Harvey (2006-08-06): new, faster algorithm, also using faster NTL interface

  • David Harvey (2007-08-31): algorithm for a single Bernoulli number mod p

  • David Harvey (2008-06): added interface to bernmm, removed old code

sage.rings.bernoulli_mod_p.bernoulli_mod_p(p)[source]#

Return the Bernoulli numbers \(B_0, B_2, ... B_{p-3}\) modulo \(p\).

INPUT:

  • p – integer, a prime

OUTPUT:

list – Bernoulli numbers modulo \(p\) as a list of integers [B(0), B(2), … B(p-3)].

ALGORITHM:

Described in accompanying latex file.

PERFORMANCE:

Should be complexity \(O(p \log p)\).

EXAMPLES:

Check the results against PARI’s C-library implementation (that computes exact rationals) for \(p = 37\):

sage: bernoulli_mod_p(37)
[1, 31, 16, 15, 16, 4, 17, 32, 22, 31, 15, 15, 17, 12, 29, 2, 0, 2]
sage: [bernoulli(n) % 37 for n in range(0, 36, 2)]
[1, 31, 16, 15, 16, 4, 17, 32, 22, 31, 15, 15, 17, 12, 29, 2, 0, 2]

>>> from sage.all import *
>>> bernoulli_mod_p(Integer(37))
[1, 31, 16, 15, 16, 4, 17, 32, 22, 31, 15, 15, 17, 12, 29, 2, 0, 2]
>>> [bernoulli(n) % Integer(37) for n in range(Integer(0), Integer(36), Integer(2))]
[1, 31, 16, 15, 16, 4, 17, 32, 22, 31, 15, 15, 17, 12, 29, 2, 0, 2]

Boundary case:

sage: bernoulli_mod_p(3)
 [1]

>>> from sage.all import *
>>> bernoulli_mod_p(Integer(3))
 [1]

AUTHOR:

  • David Harvey (2006-08-06)

sage.rings.bernoulli_mod_p.bernoulli_mod_p_single(p, k)[source]#

Return the Bernoulli number \(B_k\) mod \(p\).

If \(B_k\) is not \(p\)-integral, an ArithmeticError is raised.

INPUT:

  • p – integer, a prime

  • k – non-negative integer

OUTPUT:

The \(k\)-th Bernoulli number mod \(p\).

EXAMPLES:

sage: bernoulli_mod_p_single(1009, 48)
628
sage: bernoulli(48) % 1009
628

sage: bernoulli_mod_p_single(1, 5)
Traceback (most recent call last):
...
ValueError: p (=1) must be a prime >= 3

sage: bernoulli_mod_p_single(100, 4)
Traceback (most recent call last):
...
ValueError: p (=100) must be a prime

sage: bernoulli_mod_p_single(19, 5)
0

sage: bernoulli_mod_p_single(19, 18)
Traceback (most recent call last):
...
ArithmeticError: B_k is not integral at p

sage: bernoulli_mod_p_single(19, -4)
Traceback (most recent call last):
...
ValueError: k must be non-negative

>>> from sage.all import *
>>> bernoulli_mod_p_single(Integer(1009), Integer(48))
628
>>> bernoulli(Integer(48)) % Integer(1009)
628

>>> bernoulli_mod_p_single(Integer(1), Integer(5))
Traceback (most recent call last):
...
ValueError: p (=1) must be a prime >= 3

>>> bernoulli_mod_p_single(Integer(100), Integer(4))
Traceback (most recent call last):
...
ValueError: p (=100) must be a prime

>>> bernoulli_mod_p_single(Integer(19), Integer(5))
0

>>> bernoulli_mod_p_single(Integer(19), Integer(18))
Traceback (most recent call last):
...
ArithmeticError: B_k is not integral at p

>>> bernoulli_mod_p_single(Integer(19), -Integer(4))
Traceback (most recent call last):
...
ValueError: k must be non-negative

Check results against bernoulli_mod_p:

sage: bernoulli_mod_p(37)
 [1, 31, 16, 15, 16, 4, 17, 32, 22, 31, 15, 15, 17, 12, 29, 2, 0, 2]
sage: [bernoulli_mod_p_single(37, n) % 37 for n in range(0, 36, 2)]
 [1, 31, 16, 15, 16, 4, 17, 32, 22, 31, 15, 15, 17, 12, 29, 2, 0, 2]

sage: bernoulli_mod_p(31)
 [1, 26, 1, 17, 1, 9, 11, 27, 14, 23, 13, 22, 14, 8, 14]
sage: [bernoulli_mod_p_single(31, n) % 31 for n in range(0, 30, 2)]
 [1, 26, 1, 17, 1, 9, 11, 27, 14, 23, 13, 22, 14, 8, 14]

sage: bernoulli_mod_p(3)
 [1]
sage: [bernoulli_mod_p_single(3, n) % 3 for n in range(0, 2, 2)]
 [1]

sage: bernoulli_mod_p(5)
 [1, 1]
sage: [bernoulli_mod_p_single(5, n) % 5 for n in range(0, 4, 2)]
 [1, 1]

sage: bernoulli_mod_p(7)
 [1, 6, 3]
sage: [bernoulli_mod_p_single(7, n) % 7 for n in range(0, 6, 2)]
 [1, 6, 3]

>>> from sage.all import *
>>> bernoulli_mod_p(Integer(37))
 [1, 31, 16, 15, 16, 4, 17, 32, 22, 31, 15, 15, 17, 12, 29, 2, 0, 2]
>>> [bernoulli_mod_p_single(Integer(37), n) % Integer(37) for n in range(Integer(0), Integer(36), Integer(2))]
 [1, 31, 16, 15, 16, 4, 17, 32, 22, 31, 15, 15, 17, 12, 29, 2, 0, 2]

>>> bernoulli_mod_p(Integer(31))
 [1, 26, 1, 17, 1, 9, 11, 27, 14, 23, 13, 22, 14, 8, 14]
>>> [bernoulli_mod_p_single(Integer(31), n) % Integer(31) for n in range(Integer(0), Integer(30), Integer(2))]
 [1, 26, 1, 17, 1, 9, 11, 27, 14, 23, 13, 22, 14, 8, 14]

>>> bernoulli_mod_p(Integer(3))
 [1]
>>> [bernoulli_mod_p_single(Integer(3), n) % Integer(3) for n in range(Integer(0), Integer(2), Integer(2))]
 [1]

>>> bernoulli_mod_p(Integer(5))
 [1, 1]
>>> [bernoulli_mod_p_single(Integer(5), n) % Integer(5) for n in range(Integer(0), Integer(4), Integer(2))]
 [1, 1]

>>> bernoulli_mod_p(Integer(7))
 [1, 6, 3]
>>> [bernoulli_mod_p_single(Integer(7), n) % Integer(7) for n in range(Integer(0), Integer(6), Integer(2))]
 [1, 6, 3]

AUTHOR:

  • David Harvey (2007-08-31)

  • David Harvey (2008-06): rewrote to use bernmm library

sage.rings.bernoulli_mod_p.verify_bernoulli_mod_p(data)[source]#

Compute checksum for Bernoulli numbers.

It checks the identity

\[\sum_{n=0}^{(p-3)/2} 2^{2n} (2n+1) B_{2n} \equiv -2 \pmod p\]

(see “Irregular Primes to One Million”, Buhler et al)

INPUT:

OUTPUT: bool – True if checksum passed

EXAMPLES:

sage: from sage.rings.bernoulli_mod_p import verify_bernoulli_mod_p
sage: verify_bernoulli_mod_p(bernoulli_mod_p(next_prime(3)))
True
sage: verify_bernoulli_mod_p(bernoulli_mod_p(next_prime(1000)))
True
sage: verify_bernoulli_mod_p([1, 2, 4, 5, 4])
True
sage: verify_bernoulli_mod_p([1, 2, 3, 4, 5])
False

>>> from sage.all import *
>>> from sage.rings.bernoulli_mod_p import verify_bernoulli_mod_p
>>> verify_bernoulli_mod_p(bernoulli_mod_p(next_prime(Integer(3))))
True
>>> verify_bernoulli_mod_p(bernoulli_mod_p(next_prime(Integer(1000))))
True
>>> verify_bernoulli_mod_p([Integer(1), Integer(2), Integer(4), Integer(5), Integer(4)])
True
>>> verify_bernoulli_mod_p([Integer(1), Integer(2), Integer(3), Integer(4), Integer(5)])
False

This one should test that long longs are working:

sage: verify_bernoulli_mod_p(bernoulli_mod_p(next_prime(20000)))
True

>>> from sage.all import *
>>> verify_bernoulli_mod_p(bernoulli_mod_p(next_prime(Integer(20000))))
True

AUTHOR: David Harvey