Module integer_mod

File: sage/rings/integer_mod.pyx (starting at line 112)

Create an integer modulo $n$ with the given parent.

This is mainly for internal use. 

File: sage/rings/integer_mod.pyx (starting at line 85)

Return the equivalence class of $n$ modulo $m$ as an element of
$\Z/m\Z$.

EXAMPLES:
    sage: x = Mod(12345678, 32098203845329048)
    sage: x
    12345678
    sage: x^100
    1017322209155072

You can also use the lowercase version:
    sage: mod(12,5)
    2

File: sage/rings/integer_mod.pyx (starting at line 2780)

Return $V_k(P, 1)$ where $V_k$ is the Lucas function 
defined by the recursive relation

$V_k(P, Q) = PV_{k-1}(P, Q) -  QV_{k-2}(P, Q)$

with $V_0 = 2, V_1(P_Q) = P$.

REFERENCES: 
    H. Postl. `Fast evaluation of Dickson Polynomials'
        Contrib. to General Algebra, Vol. 6 (1988) pp. 223--225
    
AUTHOR: 
    Robert Bradshaw
    
TESTS:
    sage: from sage.rings.integer_mod import fast_lucas, slow_lucas
    sage: all([fast_lucas(k, a) == slow_lucas(k, a) 
    ...        for a in Integers(23) 
    ...        for k in range(13)])
    True

File: sage/rings/integer_mod.pyx (starting at line 138)

Return \code{True} if and only if x is an integer modulo $n$.

EXAMPLES:
    sage: is_IntegerMod(5)
    False
    sage: is_IntegerMod(Mod(5,10))
    True

File: sage/rings/integer_mod.pyx (starting at line 150)

Function to convert a Sage Integer into class NativeIntStruct.

NOTE: This function seems completely redundant, and is not used anywhere.

File: sage/rings/integer_mod.pyx (starting at line 85)

Return the equivalence class of $n$ modulo $m$ as an element of
$\Z/m\Z$.

EXAMPLES:
    sage: x = Mod(12345678, 32098203845329048)
    sage: x
    12345678
    sage: x^100
    1017322209155072

You can also use the lowercase version:
    sage: mod(12,5)
    2

File: sage/rings/integer_mod.pyx (starting at line 2677)

Calculates the square root of $a$, where $a$ is an integer mod $p$;
if $a$ is not a perfect square, this returns an (incorrect) answer
without checking.

ALGORITHM: 
    Several cases based on residue class of $p \bmod 16$.

\begin{itemize}
\item $p \bmod 2 = 0$: $p = 2$ so $\sqrt{a} = a$.
\item $p \bmod 4 = 3$: $\sqrt{a} = a^{(p+1)/4}$.
\item $p \bmod 8 = 5$: $\sqrt{a} = \zeta i a$ where $\zeta = (2a)^{(p-5)/8}$, $i=\sqrt{-1}$.
\item $p \bmod 16 = 9$: Similar, work in a bi-quadratic extension of $\FF_p$ for
                        small $p$, Tonelli and Shanks for large $p$.
\item $p \bmod 16 = 1$: Tonelli and Shanks.
\end{itemize}
    
REFERENCES: 
    Siguna M\"uller. `On the Computation of Square Roots in Finite Fields'
        Designs, Codes and Cryptography, Volume 31,  Issue 3 (March 2004)
        
    A. Oliver L. Atkin. `Probabilistic primality testing' (Section 4)
        In P. Flajolet and P. Zimmermann, editors, Analysis of Algorithms Seminar I. INRIA Research Report XXX, 1992. 
        Summary by F. Morain. 
        \url{http://citeseer.ist.psu.edu/atkin92probabilistic.html}
        
    H. Postl. `Fast evaluation of Dickson Polynomials'
        Contrib. to General Algebra, Vol. 6 (1988) pp. 223--225
    
AUTHOR:
    Robert Bradshaw
    
TESTS: 
    Every case appears in the first hundred primes. 
    sage: from sage.rings.integer_mod import square_root_mod_prime   # sqrt() uses brute force for small p
    sage: all([square_root_mod_prime(a*a)^2 == a*a 
    ...        for p in prime_range(100) 
    ...        for a in Integers(p)])
    True

File: sage/rings/integer_mod.pyx (starting at line 2620)

Calculates the square root of $a$, where $a$ is an integer mod $p^e$.

ALGORITHM: 
    Perform $p$-adically by stripping off even powers of $p$ to get
    a unit and lifting $\sqrt{unit} \bmod p$ via Newton's method.
    
AUTHOR:
    -- Robert Bradshaw

EXAMPLES:
    sage: from sage.rings.integer_mod import square_root_mod_prime_power
    sage: a=Mod(17,2^20)
    sage: b=square_root_mod_prime_power(a,2,20)
    sage: b^2 == a
    True

    sage: a=Mod(72,97^10)
    sage: b=square_root_mod_prime_power(a,97,10)
    sage: b^2 == a
    True