p_q_prime_solver_q=(p^3-p-13)_frac_(109(3p+64)).py

# Program to search p, q primes so that
# q = (p**3-p-13)/(109*(3*p+64))
# Python3 programs to do Miller-Rabin primality test
P=15000
import random
def power(x, y, p):
    res = 1
    x = x % p
    while (y > 0):
        if (y & 1):
            res = (res * x) % p
        y = y>>1; # y = y/2
        x = (x * x) % p
    return res
def miillerTest(d, n):
    a = 2 + random.randint(1, n - 4)
    x = power(a, d, n)
    if (x == 1 or x == n - 1):
        return True;
    while (d != n - 1):
        x = (x * x) % n
        d *= 2
        if (x == 1):
            return False
        if (x == n - 1):
            return True
    return False.
def prime( n, k):
    if (n <= 1 or n == 4):
        return False
    if (n <= 3):
        return True
    d = n - 1;
    while (d % 2 == 0):
        d //= 2
    for i in range(k):
        if (miillerTest(d, n) == False):
            return False
    return True
# Driver Code
# Number of iterations
k = 4
for p in range(2,P):
    if((p**3-p-13)%(109*(3*p+64))==0):
        if(prime(p,k) and prime((p**3-p-13)//(109*(3*p+64)),k)):
           print(p,(p**3-p-13)//(109*(3*p+64)))