Return to Question

Here is a working Python implementation of primality test. Is there something that I could change in code to achieve a better running time?

from sympy import *
from sympy.abc import x

n=int(input("Enter a number : "))

def xmat(r,n):
    return Matrix([[2*x, -1], [1, 0]])*rem(1,x**r-1)*(1%n)

def smallestr(n):
    if n==1 or n%2==0:
        return 0
    else:
        r=3
        while r<1000000:
            u=n%r
            if u==0 and r<n:
                return 0
            elif not(u==0) and not(u==1) and not(u==r-1):
                return r
            else:
                r=nextprime(r)

def myisprime(n):
    r=smallestr(n)
    if r==0:
        return n==2
    else:
        xp=(xmat(r,n)**n)*Matrix([[x],[1]])
        return trunc(xp[1],n)==(rem(x*(1%n),x**r-1))**n

        
if myisprime(n):
    print("prime")
else:
    print("composite")

You can run this code here.

EDIT

To clarify things, this Python code represents my attempt to translate the following PARI/GP code which is very fast.

Here is a working Python implementation of primality test. Is there something that I could change in code to achieve a better running time? For more information about algorithm see this post.

from sympy import *
from sympy.abc import x

n=int(input("Enter a number : "))

def xmat(r,n):
    return Matrix([[2*x, -1], [1, 0]])*rem(1,x**r-1)*(1%n)

def smallestr(n):
    if n==1 or n%2==0:
        return 0
    else:
        r=3
        while r<1000000:
            u=n%r
            if u==0 and r<n:
                return 0
            elif not(u==0) and not(u==1) and not(u==r-1):
                return r
            else:
                r=nextprime(r)

def myisprime(n):
    r=smallestr(n)
    if r==0:
        return n==2
    else:
        xp=(xmat(r,n)**n)*Matrix([[x],[1]])
        return trunc(xp[1],n)==(rem(x*(1%n),x**r-1))**n

        
if myisprime(n):
    print("prime")
else:
    print("composite")

You can run this code here.

EDIT

To clarify things, this Python code represents my attempt to translate the following PARI/GP code which is very fast.

Here is a working Python implementation of primality test. Is there something that I could change in code to achieve a better running time?

from sympy import *
from sympy.abc import x

n=int(input("Enter a number : "))

def xmat(r,n):
    return Matrix([[2*x, -1], [1, 0]])*rem(1,x**r-1)*(1%n)

def smallestr(n):
    if n==1 or n%2==0:
        return 0
    else:
        r=3
        while r<1000000:
            u=n%r
            if u==0 and r<n:
                return 0
            elif not(u==0) and not(u==1) and not(u==r-1):
                return r
            else:
                r=nextprime(r)

def myisprime(n):
    r=smallestr(n)
    if r==0:
        return n==2
    else:
        xp=(xmat(r,n)**n)*Matrix([[x],[1]])
        return trunc(xp[1],n)==(rem(x*(1%n),x**r-1))**n

        
if myisprime(n):
    print("prime")
else:
    print("composite")

You can run this code here.

Here is a working Python implementation of primality test. Is there something that I could change in code to achieve a better running time?

from sympy import *
from sympy.abc import x

n=int(input("Enter a number : "))

def xmat(r,n):
    return Matrix([[2*x, -1], [1, 0]])*rem(1,x**r-1)*(1%n)

def smallestr(n):
    if n==1 or n%2==0:
        return 0
    else:
        r=3
        while r<1000000:
            u=n%r
            if u==0 and r<n:
                return 0
            elif not(u==0) and not(u==1) and not(u==r-1):
                return r
            else:
                r=nextprime(r)

def myisprime(n):
    r=smallestr(n)
    if r==0:
        return n==2
    else:
        xp=(xmat(r,n)**n)*Matrix([[x],[1]])
        return trunc(xp[1],n)==(rem(x*(1%n),x**r-1))**n

        
if myisprime(n):
    print("prime")
else:
    print("composite")

You can run this code here.

EDIT

To clarify things, this Python code represents my attempt to translate the following PARI/GP code which is very fast.

Here is a working Python implementation of primality test. Is there something that I could change in code to achieve a better running time?

from sympy import *
from sympy.abc import x

n=int(input("Enter a number : "))

def xmat(r,n):
    return Matrix([[2*x, -1], [1, 0]])*rem(1,x**r-1)*(1%n)

def smallestr(n):
    if n==1 or n%2==0:
        return 0
    else:
        r=3
        while r<1000000:
            u=n%r
            if u==0 and r<n:
                return 0
            elif not(u==0) and not(u==1) and not(u==r-1):
                return r
            else:
                r=nextprime(r)

def myisprime(n):
    r=smallestr(n)
    if r==0:
        return n==2
    else:
        xp=(xmat(r,n)**n)*Matrix([[x],[1]])
        return gcd((expand(xp[1])-(rem(x*(1%n),x**r-1))**n),n)==n

        
if myisprime(n):
    print("prime")
else:
    print("composite")

You can run this code here.

Here is a working Python implementation of primality test. Is there something that I could change in code to achieve a better running time?

from sympy import *
from sympy.abc import x

n=int(input("Enter a number : "))

def xmat(r,n):
    return Matrix([[2*x, -1], [1, 0]])*rem(1,x**r-1)*(1%n)

def smallestr(n):
    if n==1 or n%2==0:
        return 0
    else:
        r=3
        while r<1000000:
            u=n%r
            if u==0 and r<n:
                return 0
            elif not(u==0) and not(u==1) and not(u==r-1):
                return r
            else:
                r=nextprime(r)

def myisprime(n):
    r=smallestr(n)
    if r==0:
        return n==2
    else:
        xp=(xmat(r,n)**n)*Matrix([[x],[1]])
        return trunc(xp[1],n)==(rem(x*(1%n),x**r-1))**n

        
if myisprime(n):
    print("prime")
else:
    print("composite")

You can run this code here.