Subsections

12. Elementary number theory


12.1 Discrete logs

To find a number $ x$ such that $ b^x\equiv a \pmod m$ (the discrete log of $ a \pmod m$ ), you can call GAP's LogMod (which uses Pollard-rho) or LogModShanks (which uses Shanks' baby-step giant-step).

sage: gap.eval("51^54 mod 97")
      '12'
sage: gap.eval("LogMod(12,51,97)")
      '54'
sage: gap.eval("LogModShanks(12,51,97)")
      '22'
sage: gap.eval("51^22 mod 97")
      '12'

Pari also has a discrete log function znlog.

sage: gp("znlog(Mod(51,97)^54, Mod(51,97))")
54


12.2 Prime numbers

Self explanatory:

sage: next_prime(2005)
      2011


12.3 Divisors

SAGE uses intuitive notation to do this.

sage: divisors(28); sum(divisors(28)); 2*28
      [1, 2, 4, 7, 14, 28]
      56
      56
sage: sigma(28,0); sigma(28,1); sigma(28,2)
      6
      56
      1050


12.4 Quadratic residues

Try this:

sage: Q = quadratic_residues(23); Q
[0, 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18]
sage: N = [x for x in range(22) if kronecker(x,23)==-1]; N
[5, 7, 10, 11, 14, 15, 17, 19, 20, 21]

Q is the set of quadratic residues mod 23 and N is the set of non-residues.

See About this document... for information on suggesting changes.