One Line.sagews

One Line Attack

Description. This attack will compute one of the primes in a composite number if the difference of the primes is small

##############################################################################################
# isquare detectes weither a number is a perfect square or not                               #
##############################################################################################
def isquare (n):
    if isqrt(n) ** 2 == n:
        return(True)
    return(False)


##############################################################################################
# isqrt takes in an integer as input and produces the floor of the square root of the number#
##############################################################################################
def isqrt(n):
    return int(floor(sqrt(n)))

##############################################################################################
# usqrt takes in a number and produces the celing of the square root of the number           #
##############################################################################################
def usqrt (n):
    ur = isqrt(n)
    if ur ** 2 < n:
        ur = ur + 1
    return(ur)

##############################################################################################
# OneLine will take in a composite nubmer and a round limit and attempt to compute one of the# 
#prime factors. If unable the function will print out that no factors have been found        #
##############################################################################################

def OneLine (n, iter):
    for x in range(1, iter + 1):
        sq = usqrt(x * n)
        y = sq ** 2 % n
        if isquare(y) == True:
            t = isqrt(y)
            u = gcd(n, sq - t)
            print("Factor found in round {0} rounds".format(x))
            return(u)
    print("No factors found")

%md 
<b>Example.</b> One case where the attack runs of reletivley small numbers

Example. One case where the attack runs of reletivley small numbers

OneLine(next_prime(113)*next_prime(129),100)

Factor found in round 1 rounds 127

Example. Another example where the attack is running with larger and more seperated primes

p = next_prime(12345678234567812345678234567)
q = next_prime(12345678234567813786785845456)
p
q
n = p*q
OneLine(n,1000000)

12345678234567812345678234591 12345678234567813786785845649 Factor found in round 1 rounds 12345678234567812345678234591