CoCalc Public FilesISAttack.sagews
Author: Liljana Babinkostova
Views : 95
Compute Environment: Ubuntu 20.04 (Default)

Initial Segment Attack

Description. This attack works if one of the primes has a lot of sequential zeros for digits base 10 and the other prime used is smaller than the ammount of zeros used. The consept of the attack is to divy up the sub numbers digit by digit and check if the gcd of that subnumber and the modulus is greater than 1.

###########################################################################################################
# The ISAttack function will attempt to return a factor of the composite number entered in as an argument #
# The attack could be successful is one of the prime has many sequental zeros as digits                   #
###########################################################################################################

def ISAttack (R):
R = ZZ(R)
n = R.ndigits()
#n = len(R)
for j in range(1, n + 1):
x=(R-(R % 10^j))/10^j
p = gcd(x, R)
if ((1 < p)and (p<R)):
return(p)
print("no factor found")

#########
#EXAMPLE#
#########
p = next_prime(1270000000000000000000000000000000000000008)
q = next_prime(456768534657687546576879676568)
p
q
n = p*q
ISAttack(n)

1270000000000000000000000000000000000000043 456768534657687546576879676661 456768534657687546576879676661