Skip to content

Instantly share code, notes, and snippets.

@maqp

maqp/recoprocal_factoring_efficiency.py

Created October 28, 2019 00:39
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save maqp/b04e27e795ab01c5cdefdcddc59e3a02 to your computer and use it in GitHub Desktop.
Save maqp/b04e27e795ab01c5cdefdcddc59e3a02 to your computer and use it in GitHub Desktop.
Download ZIP
Crown Sterling reciprocal factoring method efficiency vs trial division (brute force)
Raw
recoprocal_factoring_efficiency.py
import math
import random
from typing import List
# Let's meet our contestants
def trial_division(semiprime: int):
"""The Faster brute force variant, from Wikipedia:
https://en.wikipedia.org/wiki/Trial_division :
def trial_division(n):
a = []
while n % 2 == 0:
a.append(2)
n /= 2
f = 3
while f * f <= n:
if n % f == 0:
a.append(f)
n /= f
else:
f += 2
if n != 1:
a.append(n)
return a
"""
# `steps` will keep track of the number of steps the algorithm has gone through.
# Since the description above has multiple steps per line, the implementation
# has been altered so that only one thing is done per line. This allows more
# accurate counting of steps.
steps = 0
original_semiprime = semiprime
steps += 1
a = [] # type: List[int]
steps += 1
# Determine the initial while-loop condition
semiprime_mod_two = semiprime % 2
steps += 1
semiprime_mod_two_is_zero = semiprime_mod_two == 0
steps += 1
while semiprime_mod_two_is_zero:
steps += 1 # While condition evaluation
a.append(2)
steps += 1
semiprime = semiprime / 2
steps += 1
# Update the while-loop condition
semiprime_mod_two = semiprime % 2
steps += 1
semiprime_mod_two_is_zero = semiprime_mod_two == 0
steps += 1
steps += 1 # While condition check that evaluated false
f = 3
steps += 1
# Determine the initial while-loop condition
f_pow2 = f*f
steps += 1
f_pow2_smaller_or_equal_to_semiprime = f_pow2 <= semiprime
steps += 1
while f_pow2_smaller_or_equal_to_semiprime:
steps += 1 # While condition evaluation
# Determine the if-statement condition
semiprime_mod_f = semiprime % f
steps += 1
semiprime_mod_f_is_zero = semiprime_mod_f == 0
steps += 1
steps += 1 # If-statement evaluation
if semiprime_mod_f_is_zero:
a.append(f)
steps += 1
semiprime = semiprime / f
steps += 1
else:
f += 2
steps += 1
# Update the while-loop condition
f_pow2 = f * f
steps += 1
f_pow2_smaller_or_equal_to_semiprime = f_pow2 <= semiprime
steps += 1
steps += 1 # While condition check that evaluated false
# Determine if-statement condition
n_is_not_one = semiprime != 1
steps += 1
steps += 1 # If-statement evaluation
if n_is_not_one:
a.append(semiprime)
steps += 1
# Determine factors
factor_1 = a[0]
steps += 1
# We have the first factor, so we get the another by dividing the semiprime with the first factor.
factor_2 = original_semiprime // factor_1
steps += 1
steps += 1 # Add one step for return statement before returning
return original_semiprime, factor_1, factor_2, steps
def reciprocal_factoring_method(semiprime: int):
"""\
The next contestant is the Crown Sterling Reciprocal Factoring Method.
This contestant is built from the period solving algorithm by
ChitraNayal, which can be found from
https://www.geeksforgeeks.org/find-length-period-decimal-value-1n/ :
def getPeriod( n) :
'''Function to find length of period in 1/n'''
# Find the (n+1)th remainder after decimal point in value of 1/n
rem = 1 # Initialize remainder
for i in range(1, n + 2):
rem = (10 * rem) % n
# Store (n+1)th remainder
d = rem
# Count the number of remainders before next occurrence of (n+1)'th remainder 'd'
count = 0
rem = (10 * rem) % n
count += 1
while rem != d :
rem = (10 * rem) % n
count += 1
return count
"""
def digits_in_integer(integer):
"""Returns the number of digits in an integer and the number of steps required to obtain them."""
steps_ = 0
log_10_integer_float = math.log10(integer)
steps_ += 1
log_10_integer = int(log_10_integer_float)
steps_ += 1
log_10_integer_plus_one = log_10_integer + 1
steps_ += 1
# This function exists to improve readability, thus we do not add steps for returning.
return log_10_integer_plus_one, steps_
# `steps` will keep track of the number of steps the algorithm has gone through.
# Since the description above has multiple steps per line, the implementation
# has been altered so that only one thing is done per line. This allows more
# accurate counting of steps.
steps = 0
# Initialize remainder
remainder = 1 # type: int
steps += 1
# Determine prime factor length (number of digits) from the semiprime
digits_in_semiprime, steps_to_determine_digits = digits_in_integer(semiprime)
steps += steps_to_determine_digits
prime_factor_length = digits_in_semiprime // 2
steps += 1
substring = '' # substring will store our constantly updating prime factor candidate
steps += 1
substring_len = 0
steps += 1
semiprime_plus_one_th_remainder = semiprime + 1
steps += 1
period_not_exhausted = True
steps += 1
substring_long_enough = False
steps += 1
i = 1
steps += 1
# The outer loop that produces remainders that are essentially chunks of decimal expansions
while period_not_exhausted:
steps += 1 # Evaluation of period_not_exhausted
# Update period_not_exhausted
i += 1
steps += 1
period_not_exhausted = i <= semiprime_plus_one_th_remainder
steps += 1
# Generate next remainder (=decimal expansion chunk)
ten_times_remainder = 10 * remainder
steps += 1
remainder = ten_times_remainder % semiprime
steps += 1
# ---- Processing of decimal expansion for factoring starts ----
remainder_str = str(remainder)
steps += 1
remainder_str_len, steps_to_determine_digits = digits_in_integer(remainder)
steps += steps_to_determine_digits
# Determine the initial while-loop condition
remainder_index = 0
steps += 1
remainder_has_digits = remainder_index < remainder_str_len
steps += 1
# The inner loop that iterates over individual decimal digits of the decimal expansion chunk to update
# the prime factor candidate, and that then attempts to evenly divide the semiprime with the candidate.
while remainder_has_digits:
steps += 1 # While loop evaluation
# Get the next digit
next_digit_str = remainder_str[remainder_index]
steps += 1
# Update the while-loop condition
remainder_index += 1
steps += 1
remainder_has_digits = remainder_index < remainder_str_len
steps += 1
# Append the next decimal as the least significant digit (LSD) to the substring
substring += next_digit_str
steps += 1
steps += 1 # if-statement check
if not substring_long_enough:
substring_len += 1 # We know `next_digit_str` was appended above so it's safe to assume length increased by one
steps += 1
steps += 1 # if-statement check
if substring_len == prime_factor_length:
substring_long_enough = True
steps += 1
steps += 1 # if-statement check
if substring_long_enough:
factor_candidate = int(substring)
steps += 1
# Slice most significant digit (MSD) from substring for next round, e.g.
substring = substring[1:]
steps += 1
# No integer can be divided with zero and every integer can be divided with
# one so we stop processing these factor candidates ASAP for efficiency.
factor_candidate_is_zero_or_one = factor_candidate < 2
steps += 1
steps += 1 # if-statement check
if factor_candidate_is_zero_or_one:
steps += 1 # Bail out jump instruction is also a step
continue
# Check if substring divides the semiprime evenly
modulus = semiprime % factor_candidate
steps += 1
modulus_is_zero = modulus == 0
steps += 1
steps += 1 # if-statement check
if modulus_is_zero:
# Success! Now we just obtain the second prime factor
# by dividing the semiprime with the first prime factor.
another_prime_factor = semiprime // factor_candidate
steps += 1
steps += 1 # Add one step for return statement before returning
return semiprime, factor_candidate, another_prime_factor, steps
steps += 1 # `while(remainder_has_digits) evaluated as False`, we jump back to outer loop
# If we reach this point, we have iterated through the entire period without finding a prime factor.
# It thus makes no sense to continue the algorithm further to determine the period of the reciprocal.
# We therefore return None and rule the search a failure.
return None, None, None, None
# The rest of the period checking algorithm is commented out as unnecessary:
# Store (n+1)th remainder
# d = rem
# # Count the number of remainders before
# # next occurrence of (n+1)'th remainder 'd'
# count = 0
# rem = (10 * rem) % semiprime
# count += 1
# while rem != d:
# rem = (10 * rem) % semiprime
# count += 1
# Challenges
def generate_random_prime_smaller_than(n) -> int:
"""Returns a random prime smaller than n.
Based on
https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n/3035188#3035188
"""
sys_random = random.SystemRandom()
sieve = [True] * n
for i in range(3, int(n ** 0.5) + 1, 2):
if sieve[i]:
sieve[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
list_of_primes = [2] + [i for i in range(3, n, 2) if sieve[i]]
return sys_random.choice(list_of_primes)
def generate_prime_between(min_, max_):
"""Create prime between min and max numbers."""
while True:
prime = generate_random_prime_smaller_than(max_)
if prime < min_:
if debug:
print(f"generate_prime_between(): Generated too small prime {prime} (should have been >{min_})")
continue
if debug:
print(f"generate_prime_between(): Generated prime {prime}")
return prime
def create_challenge(semiprime_bit_strength, list_of_previous_challenges,
repeated_challenges_before_exit):
"""Create a challenge for a round"""
prime_bit_strength = semiprime_bit_strength // 2
prime_upper_limit = 2 ** prime_bit_strength
prime_lower_limit = int(prime_upper_limit // 2)
while True:
repeats = 0
prime1 = generate_prime_between(prime_lower_limit, prime_upper_limit)
prime2 = generate_prime_between(prime_lower_limit, prime_upper_limit)
semiprime_challenge = prime1 * prime2
if semiprime_challenge in list_of_previous_challenges:
repeats += 1
if repeats >= repeated_challenges_before_exit:
print(f"Generated too many consecutive identical games ({repeats}).\n"
"RNG is probably running out of challenges. Try larger primes\n"
"or wider range of allowed primes. Exiting.")
exit(1)
else:
break
return semiprime_challenge, prime1, prime2
def main():
"""\
This program plays a number of games to compare semiprime factoring
speed of different algorithms.
Each contestant (algorithm) is given a random semiprime to factor.
Each algorithm will then return their prime factors and the number
of steps it took to produce them. The game host will then compare
the two to determine which algorithm was more efficient.
"""
# Game management
list_of_previous_challenges = []
repeated_challenges_before_exit = 10
# Rules
semiprime_bit_strength = 32
number_of_rounds = 100
# Evaluation
efficiency_list = []
show_rounds = True
round_number = 0
while round_number < number_of_rounds:
semiprime_challenge, prime1, prime2 = create_challenge(semiprime_bit_strength,
list_of_previous_challenges,
repeated_challenges_before_exit)
# Our first contestant is the Crown Sterling Reciprocal Factoring
# Method reproduced in good faith to be as efficient as possible:
# https://www.instagram.com/p/B2HwOirnHH2/?utm_source=ig_web_copy_link
cs_semiprime, cs_factor1, cs_factor2, cs_steps = reciprocal_factoring_method(semiprime_challenge)
if cs_factor1 is None:
# Since the Crown Sterling Reciprocal Factoring method only works with some semi-primes,
# e.g., in ______
# 1/(11*13) = 1/143 = 0.006993
# neither 11 nor 13 appears in the decimal expantion of the
# reciprocal of the semiprime. So if the search fails, we'll
# be fair and give them a new chance with another semiprime
# challenge.
continue
else:
# If the Crown Sterling algorithm returned purported prime factors, we count the round as a fair battle.
round_number += 1
# Our second contestant is the trial division, the most laborious (read: least
# efficient, the same as brute force) method for finding prime factors.
trial_semiprime, trial_factor1, trial_factor2, trial_steps = trial_division(semiprime_challenge)
# Both contestants have now provided their purported prime factors and
# the number of steps they had to go through in order to produce them.
# We first verify that the factors are correct.
if not cs_factor1 * cs_factor2 == semiprime_challenge:
print(f"Oh no! Crown Sterling failed factoring {semiprime_challenge}! Competition ends!")
exit(1)
if not trial_factor1 * trial_factor2 == semiprime_challenge:
print(f"Oh no! Trial division failed factoring {semiprime_challenge}! Competition ends!")
exit(1)
# Both algorithms were correct! Time to see which one was more efficient during this round.
# We will represent the the efficiency of Crown Sterling method with a decimal value:
# 0.5 means Crown Sterling is twice as fast
# 2.0 means Crown Sterling twice as slow
cs_efficiency = cs_steps / trial_steps
# Well then add the result to a list for later evaluation of average score.
efficiency_list.append(cs_efficiency)
# We can observe per-round performance here:
if show_rounds:
challenge_whitespace = (13 - len(str(round_number))) * ' '
print(f"Challenge {round_number}:{challenge_whitespace} Factor {semiprime_challenge} | Solution: {prime1} * {prime2} (not shown to contestants)")
print(f"Trial division: {trial_factor1} * {trial_factor2} = {trial_semiprime} -- Steps: {trial_steps}")
print(f"Crown Sterling: {cs_factor1 } * {cs_factor2 } = {cs_semiprime } -- Steps: {cs_steps }")
print('--------------------------------------------------------------------------------------------------')
# We have now played all rounds of the game!
# Time to calculate the average efficiency of Crown Sterling method compared to brute force method!
avg_cs_efficiency = sum(efficiency_list) / len(efficiency_list)
# Depending on which one wins, we'll describe it a bit differently, because
# it's hard to understand "x was 0.5 times faster than y" but
# it's easy to understand "x was 2.0 times slower than y" (both mean the same thing).
result = ( f"{ avg_cs_efficiency:.2f} times slower" if avg_cs_efficiency > 1
else f"{(1/avg_cs_efficiency):.2f} times faster")
print(f"After {number_of_rounds} games played with {semiprime_bit_strength}-bit RSA public keys, on average, the Crown Sterling\n"
f"Reciprocal Factoring method was {result} than trial division (brute force).")
if __name__ == '__main__':
debug = False
main()
# Example output:
#
# Challenge 1: Factor 2847223381 | Solution: 44483 * 64007 (not shown to contestants)
# Trial division: 44483 * 64007 = 2847223381 -- Steps: 155703
# Crown Sterling: 64007 * 44483 = 2847223381 -- Steps: 748147
# --------------------------------------------------------------------------------------------------
# Challenge 2: Factor 1961821091 | Solution: 45557 * 43063 (not shown to contestants)
# Trial division: 43063 * 45557 = 1961821091 -- Steps: 150733
# Crown Sterling: 45557 * 43063 = 1961821091 -- Steps: 258529
# --------------------------------------------------------------------------------------------------
# Challenge 3: Factor 1574233009 | Solution: 42571 * 36979 (not shown to contestants)
# Trial division: 36979 * 42571 = 1574233009 -- Steps: 129439
# Crown Sterling: 36979 * 42571 = 1574233009 -- Steps: 78415
# --------------------------------------------------------------------------------------------------
# Challenge 4: Factor 2397054277 | Solution: 54371 * 44087 (not shown to contestants)
# Trial division: 44087 * 54371 = 2397054277 -- Steps: 154317
# Crown Sterling: 44087 * 54371 = 2397054277 -- Steps: 67005
# --------------------------------------------------------------------------------------------------
# Challenge 5: Factor 1400704219 | Solution: 36109 * 38791 (not shown to contestants)
# Trial division: 36109 * 38791 = 1400704219 -- Steps: 126394
# Crown Sterling: 38791 * 36109 = 1400704219 -- Steps: 1181057
# --------------------------------------------------------------------------------------------------
# Challenge 6: Factor 2154222403 | Solution: 45779 * 47057 (not shown to contestants)
# Trial division: 45779 * 47057 = 2154222403 -- Steps: 160239
# Crown Sterling: 45779 * 47057 = 2154222403 -- Steps: 2475353
# --------------------------------------------------------------------------------------------------
# Challenge 7: Factor 1730003747 | Solution: 36943 * 46829 (not shown to contestants)
# Trial division: 36943 * 46829 = 1730003747 -- Steps: 129313
# Crown Sterling: 46829 * 36943 = 1730003747 -- Steps: 1079727
# --------------------------------------------------------------------------------------------------
# Challenge 8: Factor 2445979901 | Solution: 64451 * 37951 (not shown to contestants)
# Trial division: 37951 * 64451 = 2445979901 -- Steps: 132841
# Crown Sterling: 37951 * 64451 = 2445979901 -- Steps: 50727
# --------------------------------------------------------------------------------------------------
# Challenge 9: Factor 1925247601 | Solution: 49757 * 38693 (not shown to contestants)
# Trial division: 38693 * 49757 = 1925247601 -- Steps: 135438
# Crown Sterling: 38693 * 49757 = 1925247601 -- Steps: 94283
# --------------------------------------------------------------------------------------------------
# Challenge 10: Factor 2374791311 | Solution: 50291 * 47221 (not shown to contestants)
# Trial division: 47221 * 50291 = 2374791311 -- Steps: 165286
# Crown Sterling: 50291 * 47221 = 2374791311 -- Steps: 1575887
# --------------------------------------------------------------------------------------------------
# Challenge 11: Factor 2216502961 | Solution: 37123 * 59707 (not shown to contestants)
# Trial division: 37123 * 59707 = 2216502961 -- Steps: 129943
# Crown Sterling: 37123 * 59707 = 2216502961 -- Steps: 3994859
# --------------------------------------------------------------------------------------------------
# Challenge 12: Factor 1509640609 | Solution: 34171 * 44179 (not shown to contestants)
# Trial division: 34171 * 44179 = 1509640609 -- Steps: 119611
# Crown Sterling: 44179 * 34171 = 1509640609 -- Steps: 1934783
# --------------------------------------------------------------------------------------------------
# Challenge 13: Factor 2042448341 | Solution: 42407 * 48163 (not shown to contestants)
# Trial division: 42407 * 48163 = 2042448341 -- Steps: 148437
# Crown Sterling: 48163 * 42407 = 2042448341 -- Steps: 56755
# --------------------------------------------------------------------------------------------------
# Challenge 14: Factor 2264118709 | Solution: 37951 * 59659 (not shown to contestants)
# Trial division: 37951 * 59659 = 2264118709 -- Steps: 132841
# Crown Sterling: 37951 * 59659 = 2264118709 -- Steps: 1394699
# --------------------------------------------------------------------------------------------------
# Challenge 15: Factor 3490373179 | Solution: 60737 * 57467 (not shown to contestants)
# Trial division: 57467 * 60737 = 3490373179 -- Steps: 201147
# Crown Sterling: 57467 * 60737 = 3490373179 -- Steps: 714623
# --------------------------------------------------------------------------------------------------
# Challenge 16: Factor 1727738351 | Solution: 38651 * 44701 (not shown to contestants)
# Trial division: 38651 * 44701 = 1727738351 -- Steps: 135291
# Crown Sterling: 38651 * 44701 = 1727738351 -- Steps: 305003
# --------------------------------------------------------------------------------------------------
# Challenge 17: Factor 2968145767 | Solution: 46727 * 63521 (not shown to contestants)
# Trial division: 46727 * 63521 = 2968145767 -- Steps: 163557
# Crown Sterling: 63521 * 46727 = 2968145767 -- Steps: 1307581
# --------------------------------------------------------------------------------------------------
# Challenge 18: Factor 1707754241 | Solution: 39157 * 43613 (not shown to contestants)
# Trial division: 39157 * 43613 = 1707754241 -- Steps: 137062
# Crown Sterling: 43613 * 39157 = 1707754241 -- Steps: 59957
# --------------------------------------------------------------------------------------------------
# Challenge 19: Factor 3607071817 | Solution: 59951 * 60167 (not shown to contestants)
# Trial division: 59951 * 60167 = 3607071817 -- Steps: 209841
# Crown Sterling: 60167 * 59951 = 3607071817 -- Steps: 1337483
# --------------------------------------------------------------------------------------------------
# Challenge 20: Factor 1963686161 | Solution: 34513 * 56897 (not shown to contestants)
# Trial division: 34513 * 56897 = 1963686161 -- Steps: 120808
# Crown Sterling: 34513 * 56897 = 1963686161 -- Steps: 821037
# --------------------------------------------------------------------------------------------------
# Challenge 21: Factor 2028182249 | Solution: 60289 * 33641 (not shown to contestants)
# Trial division: 33641 * 60289 = 2028182249 -- Steps: 117756
# Crown Sterling: 33641 * 60289 = 2028182249 -- Steps: 1312247
# --------------------------------------------------------------------------------------------------
# Challenge 22: Factor 2182606747 | Solution: 62057 * 35171 (not shown to contestants)
# Trial division: 35171 * 62057 = 2182606747 -- Steps: 123111
# Crown Sterling: 35171 * 62057 = 2182606747 -- Steps: 305109
# --------------------------------------------------------------------------------------------------
# Challenge 23: Factor 2696153531 | Solution: 46301 * 58231 (not shown to contestants)
# Trial division: 46301 * 58231 = 2696153531 -- Steps: 162066
# Crown Sterling: 58231 * 46301 = 2696153531 -- Steps: 534275
# --------------------------------------------------------------------------------------------------
# Challenge 24: Factor 2074733581 | Solution: 36137 * 57413 (not shown to contestants)
# Trial division: 36137 * 57413 = 2074733581 -- Steps: 126492
# Crown Sterling: 36137 * 57413 = 2074733581 -- Steps: 739173
# --------------------------------------------------------------------------------------------------
# Challenge 25: Factor 2219715583 | Solution: 59419 * 37357 (not shown to contestants)
# Trial division: 37357 * 59419 = 2219715583 -- Steps: 130762
# Crown Sterling: 37357 * 59419 = 2219715583 -- Steps: 649449
# --------------------------------------------------------------------------------------------------
# Challenge 26: Factor 2346430511 | Solution: 47819 * 49069 (not shown to contestants)
# Trial division: 47819 * 49069 = 2346430511 -- Steps: 167379
# Crown Sterling: 47819 * 49069 = 2346430511 -- Steps: 153803
# --------------------------------------------------------------------------------------------------
# Challenge 27: Factor 2616806551 | Solution: 41887 * 62473 (not shown to contestants)
# Trial division: 41887 * 62473 = 2616806551 -- Steps: 146617
# Crown Sterling: 41887 * 62473 = 2616806551 -- Steps: 2447163
# --------------------------------------------------------------------------------------------------
# Challenge 28: Factor 1996561283 | Solution: 59729 * 33427 (not shown to contestants)
# Trial division: 33427 * 59729 = 1996561283 -- Steps: 117007
# Crown Sterling: 33427 * 59729 = 1996561283 -- Steps: 95361
# --------------------------------------------------------------------------------------------------
# Challenge 29: Factor 2906497183 | Solution: 53831 * 53993 (not shown to contestants)
# Trial division: 53831 * 53993 = 2906497183 -- Steps: 188421
# Crown Sterling: 53993 * 53831 = 2906497183 -- Steps: 721901
# --------------------------------------------------------------------------------------------------
# Challenge 30: Factor 1895745451 | Solution: 56713 * 33427 (not shown to contestants)
# Trial division: 33427 * 56713 = 1895745451 -- Steps: 117007
# Crown Sterling: 56713 * 33427 = 1895745451 -- Steps: 492181
# --------------------------------------------------------------------------------------------------
# Challenge 31: Factor 2406773717 | Solution: 65173 * 36929 (not shown to contestants)
# Trial division: 36929 * 65173 = 2406773717 -- Steps: 129264
# Crown Sterling: 65173 * 36929 = 2406773717 -- Steps: 213095
# --------------------------------------------------------------------------------------------------
# Challenge 32: Factor 3473145671 | Solution: 53987 * 64333 (not shown to contestants)
# Trial division: 53987 * 64333 = 3473145671 -- Steps: 188967
# Crown Sterling: 64333 * 53987 = 3473145671 -- Steps: 482019
# --------------------------------------------------------------------------------------------------
# Challenge 33: Factor 3412015741 | Solution: 55987 * 60943 (not shown to contestants)
# Trial division: 55987 * 60943 = 3412015741 -- Steps: 195967
# Crown Sterling: 60943 * 55987 = 3412015741 -- Steps: 466921
# --------------------------------------------------------------------------------------------------
# Challenge 34: Factor 1881706991 | Solution: 40253 * 46747 (not shown to contestants)
# Trial division: 40253 * 46747 = 1881706991 -- Steps: 140898
# Crown Sterling: 40253 * 46747 = 1881706991 -- Steps: 684365
# --------------------------------------------------------------------------------------------------
# Challenge 35: Factor 3056031409 | Solution: 63179 * 48371 (not shown to contestants)
# Trial division: 48371 * 63179 = 3056031409 -- Steps: 169311
# Crown Sterling: 48371 * 63179 = 3056031409 -- Steps: 203069
# --------------------------------------------------------------------------------------------------
# Challenge 36: Factor 1958535899 | Solution: 51229 * 38231 (not shown to contestants)
# Trial division: 38231 * 51229 = 1958535899 -- Steps: 133821
# Crown Sterling: 38231 * 51229 = 1958535899 -- Steps: 1577847
# --------------------------------------------------------------------------------------------------
# Challenge 37: Factor 1625855981 | Solution: 42089 * 38629 (not shown to contestants)
# Trial division: 38629 * 42089 = 1625855981 -- Steps: 135214
# Crown Sterling: 38629 * 42089 = 1625855981 -- Steps: 1979449
# --------------------------------------------------------------------------------------------------
# Challenge 38: Factor 1333327469 | Solution: 38851 * 34319 (not shown to contestants)
# Trial division: 34319 * 38851 = 1333327469 -- Steps: 120129
# Crown Sterling: 38851 * 34319 = 1333327469 -- Steps: 488695
# --------------------------------------------------------------------------------------------------
# Challenge 39: Factor 1940210197 | Solution: 52301 * 37097 (not shown to contestants)
# Trial division: 37097 * 52301 = 1940210197 -- Steps: 129852
# Crown Sterling: 37097 * 52301 = 1940210197 -- Steps: 632075
# --------------------------------------------------------------------------------------------------
# Challenge 40: Factor 1578407057 | Solution: 36761 * 42937 (not shown to contestants)
# Trial division: 36761 * 42937 = 1578407057 -- Steps: 128676
# Crown Sterling: 42937 * 36761 = 1578407057 -- Steps: 487113
# --------------------------------------------------------------------------------------------------
# Challenge 41: Factor 2745348679 | Solution: 55049 * 49871 (not shown to contestants)
# Trial division: 49871 * 55049 = 2745348679 -- Steps: 174561
# Crown Sterling: 55049 * 49871 = 2745348679 -- Steps: 602661
# --------------------------------------------------------------------------------------------------
# Challenge 42: Factor 2499983363 | Solution: 51511 * 48533 (not shown to contestants)
# Trial division: 48533 * 51511 = 2499983363 -- Steps: 169878
# Crown Sterling: 51511 * 48533 = 2499983363 -- Steps: 24527
# --------------------------------------------------------------------------------------------------
# Challenge 43: Factor 2901504743 | Solution: 47363 * 61261 (not shown to contestants)
# Trial division: 47363 * 61261 = 2901504743 -- Steps: 165783
# Crown Sterling: 61261 * 47363 = 2901504743 -- Steps: 379339
# --------------------------------------------------------------------------------------------------
# Challenge 44: Factor 2645555287 | Solution: 42239 * 62633 (not shown to contestants)
# Trial division: 42239 * 62633 = 2645555287 -- Steps: 147849
# Crown Sterling: 42239 * 62633 = 2645555287 -- Steps: 611831
# --------------------------------------------------------------------------------------------------
# Challenge 45: Factor 1905137071 | Solution: 46511 * 40961 (not shown to contestants)
# Trial division: 40961 * 46511 = 1905137071 -- Steps: 143376
# Crown Sterling: 46511 * 40961 = 1905137071 -- Steps: 250713
# --------------------------------------------------------------------------------------------------
# Challenge 46: Factor 2905875703 | Solution: 47543 * 61121 (not shown to contestants)
# Trial division: 47543 * 61121 = 2905875703 -- Steps: 166413
# Crown Sterling: 47543 * 61121 = 2905875703 -- Steps: 15553
# --------------------------------------------------------------------------------------------------
# Challenge 47: Factor 3414744259 | Solution: 64601 * 52859 (not shown to contestants)
# Trial division: 52859 * 64601 = 3414744259 -- Steps: 185019
# Crown Sterling: 64601 * 52859 = 3414744259 -- Steps: 865935
# --------------------------------------------------------------------------------------------------
# Challenge 48: Factor 2972555387 | Solution: 57649 * 51563 (not shown to contestants)
# Trial division: 51563 * 57649 = 2972555387 -- Steps: 180483
# Crown Sterling: 51563 * 57649 = 2972555387 -- Steps: 1001485
# --------------------------------------------------------------------------------------------------
# Challenge 49: Factor 2150781131 | Solution: 61657 * 34883 (not shown to contestants)
# Trial division: 34883 * 61657 = 2150781131 -- Steps: 122103
# Crown Sterling: 34883 * 61657 = 2150781131 -- Steps: 28807
# --------------------------------------------------------------------------------------------------
# Challenge 50: Factor 1704203447 | Solution: 44851 * 37997 (not shown to contestants)
# Trial division: 37997 * 44851 = 1704203447 -- Steps: 133002
# Crown Sterling: 44851 * 37997 = 1704203447 -- Steps: 74171
# --------------------------------------------------------------------------------------------------
# Challenge 51: Factor 2928554263 | Solution: 52181 * 56123 (not shown to contestants)
# Trial division: 52181 * 56123 = 2928554263 -- Steps: 182646
# Crown Sterling: 56123 * 52181 = 2928554263 -- Steps: 564325
# --------------------------------------------------------------------------------------------------
# Challenge 52: Factor 3001847249 | Solution: 53407 * 56207 (not shown to contestants)
# Trial division: 53407 * 56207 = 3001847249 -- Steps: 186937
# Crown Sterling: 53407 * 56207 = 3001847249 -- Steps: 157119
# --------------------------------------------------------------------------------------------------
# Challenge 53: Factor 3263322563 | Solution: 54319 * 60077 (not shown to contestants)
# Trial division: 54319 * 60077 = 3263322563 -- Steps: 190129
# Crown Sterling: 54319 * 60077 = 3263322563 -- Steps: 3311437
# --------------------------------------------------------------------------------------------------
# Challenge 54: Factor 3303633131 | Solution: 54979 * 60089 (not shown to contestants)
# Trial division: 54979 * 60089 = 3303633131 -- Steps: 192439
# Crown Sterling: 60089 * 54979 = 3303633131 -- Steps: 36245
# --------------------------------------------------------------------------------------------------
# Challenge 55: Factor 2153545903 | Solution: 61283 * 35141 (not shown to contestants)
# Trial division: 35141 * 61283 = 2153545903 -- Steps: 123006
# Crown Sterling: 35141 * 61283 = 2153545903 -- Steps: 24897
# --------------------------------------------------------------------------------------------------
# Challenge 56: Factor 3218855881 | Solution: 50773 * 63397 (not shown to contestants)
# Trial division: 50773 * 63397 = 3218855881 -- Steps: 177718
# Crown Sterling: 63397 * 50773 = 3218855881 -- Steps: 563753
# --------------------------------------------------------------------------------------------------
# Challenge 57: Factor 2874456661 | Solution: 51239 * 56099 (not shown to contestants)
# Trial division: 51239 * 56099 = 2874456661 -- Steps: 179349
# Crown Sterling: 51239 * 56099 = 2874456661 -- Steps: 35785
# --------------------------------------------------------------------------------------------------
# Challenge 58: Factor 1550385247 | Solution: 42299 * 36653 (not shown to contestants)
# Trial division: 36653 * 42299 = 1550385247 -- Steps: 128298
# Crown Sterling: 42299 * 36653 = 1550385247 -- Steps: 1093703
# --------------------------------------------------------------------------------------------------
# Challenge 59: Factor 2351689189 | Solution: 35969 * 65381 (not shown to contestants)
# Trial division: 35969 * 65381 = 2351689189 -- Steps: 125904
# Crown Sterling: 65381 * 35969 = 2351689189 -- Steps: 227149
# --------------------------------------------------------------------------------------------------
# Challenge 60: Factor 2617576397 | Solution: 42307 * 61871 (not shown to contestants)
# Trial division: 42307 * 61871 = 2617576397 -- Steps: 148087
# Crown Sterling: 42307 * 61871 = 2617576397 -- Steps: 192449
# --------------------------------------------------------------------------------------------------
# Challenge 61: Factor 3369432893 | Solution: 57901 * 58193 (not shown to contestants)
# Trial division: 57901 * 58193 = 3369432893 -- Steps: 202666
# Crown Sterling: 58193 * 57901 = 3369432893 -- Steps: 330851
# --------------------------------------------------------------------------------------------------
# Challenge 62: Factor 1659322019 | Solution: 47837 * 34687 (not shown to contestants)
# Trial division: 34687 * 47837 = 1659322019 -- Steps: 121417
# Crown Sterling: 47837 * 34687 = 1659322019 -- Steps: 1492089
# --------------------------------------------------------------------------------------------------
# Challenge 63: Factor 3608122013 | Solution: 64301 * 56113 (not shown to contestants)
# Trial division: 56113 * 64301 = 3608122013 -- Steps: 196408
# Crown Sterling: 56113 * 64301 = 3608122013 -- Steps: 1124283
# --------------------------------------------------------------------------------------------------
# Challenge 64: Factor 2705834749 | Solution: 65171 * 41519 (not shown to contestants)
# Trial division: 41519 * 65171 = 2705834749 -- Steps: 145329
# Crown Sterling: 41519 * 65171 = 2705834749 -- Steps: 1271637
# --------------------------------------------------------------------------------------------------
# Challenge 65: Factor 3033244651 | Solution: 60637 * 50023 (not shown to contestants)
# Trial division: 50023 * 60637 = 3033244651 -- Steps: 175093
# Crown Sterling: 50023 * 60637 = 3033244651 -- Steps: 3695845
# --------------------------------------------------------------------------------------------------
# Challenge 66: Factor 2722873973 | Solution: 65267 * 41719 (not shown to contestants)
# Trial division: 41719 * 65267 = 2722873973 -- Steps: 146029
# Crown Sterling: 65267 * 41719 = 2722873973 -- Steps: 143625
# --------------------------------------------------------------------------------------------------
# Challenge 67: Factor 1969190789 | Solution: 38153 * 51613 (not shown to contestants)
# Trial division: 38153 * 51613 = 1969190789 -- Steps: 133548
# Crown Sterling: 38153 * 51613 = 1969190789 -- Steps: 169761
# --------------------------------------------------------------------------------------------------
# Challenge 68: Factor 1930835029 | Solution: 34591 * 55819 (not shown to contestants)
# Trial division: 34591 * 55819 = 1930835029 -- Steps: 121081
# Crown Sterling: 34591 * 55819 = 1930835029 -- Steps: 1169223
# --------------------------------------------------------------------------------------------------
# Challenge 69: Factor 3937912037 | Solution: 60899 * 64663 (not shown to contestants)
# Trial division: 60899 * 64663 = 3937912037 -- Steps: 213159
# Crown Sterling: 60899 * 64663 = 3937912037 -- Steps: 189167
# --------------------------------------------------------------------------------------------------
# Challenge 70: Factor 2502608359 | Solution: 46933 * 53323 (not shown to contestants)
# Trial division: 46933 * 53323 = 2502608359 -- Steps: 164278
# Crown Sterling: 46933 * 53323 = 2502608359 -- Steps: 1092031
# --------------------------------------------------------------------------------------------------
# Challenge 71: Factor 1850700931 | Solution: 36997 * 50023 (not shown to contestants)
# Trial division: 36997 * 50023 = 1850700931 -- Steps: 129502
# Crown Sterling: 50023 * 36997 = 1850700931 -- Steps: 3752289
# --------------------------------------------------------------------------------------------------
# Challenge 72: Factor 1677736969 | Solution: 40483 * 41443 (not shown to contestants)
# Trial division: 40483 * 41443 = 1677736969 -- Steps: 141703
# Crown Sterling: 40483 * 41443 = 1677736969 -- Steps: 734277
# --------------------------------------------------------------------------------------------------
# Challenge 73: Factor 2938861297 | Solution: 58393 * 50329 (not shown to contestants)
# Trial division: 50329 * 58393 = 2938861297 -- Steps: 176164
# Crown Sterling: 50329 * 58393 = 2938861297 -- Steps: 1381727
# --------------------------------------------------------------------------------------------------
# Challenge 74: Factor 1836470413 | Solution: 33083 * 55511 (not shown to contestants)
# Trial division: 33083 * 55511 = 1836470413 -- Steps: 115803
# Crown Sterling: 55511 * 33083 = 1836470413 -- Steps: 268105
# --------------------------------------------------------------------------------------------------
# Challenge 75: Factor 2189451853 | Solution: 57287 * 38219 (not shown to contestants)
# Trial division: 38219 * 57287 = 2189451853 -- Steps: 133779
# Crown Sterling: 38219 * 57287 = 2189451853 -- Steps: 869427
# --------------------------------------------------------------------------------------------------
# Challenge 76: Factor 2225315789 | Solution: 47581 * 46769 (not shown to contestants)
# Trial division: 46769 * 47581 = 2225315789 -- Steps: 163704
# Crown Sterling: 46769 * 47581 = 2225315789 -- Steps: 952725
# --------------------------------------------------------------------------------------------------
# Challenge 77: Factor 2128061191 | Solution: 56629 * 37579 (not shown to contestants)
# Trial division: 37579 * 56629 = 2128061191 -- Steps: 131539
# Crown Sterling: 37579 * 56629 = 2128061191 -- Steps: 1349269
# --------------------------------------------------------------------------------------------------
# Challenge 78: Factor 3664054969 | Solution: 62581 * 58549 (not shown to contestants)
# Trial division: 58549 * 62581 = 3664054969 -- Steps: 204934
# Crown Sterling: 62581 * 58549 = 3664054969 -- Steps: 2486315
# --------------------------------------------------------------------------------------------------
# Challenge 79: Factor 2310515983 | Solution: 48197 * 47939 (not shown to contestants)
# Trial division: 47939 * 48197 = 2310515983 -- Steps: 167799
# Crown Sterling: 47939 * 48197 = 2310515983 -- Steps: 2381239
# --------------------------------------------------------------------------------------------------
# Challenge 80: Factor 1526356417 | Solution: 39503 * 38639 (not shown to contestants)
# Trial division: 38639 * 39503 = 1526356417 -- Steps: 135249
# Crown Sterling: 39503 * 38639 = 1526356417 -- Steps: 1248011
# --------------------------------------------------------------------------------------------------
# Challenge 81: Factor 3192055367 | Solution: 63799 * 50033 (not shown to contestants)
# Trial division: 50033 * 63799 = 3192055367 -- Steps: 175128
# Crown Sterling: 63799 * 50033 = 3192055367 -- Steps: 117077
# --------------------------------------------------------------------------------------------------
# Challenge 82: Factor 3259854461 | Solution: 64489 * 50549 (not shown to contestants)
# Trial division: 50549 * 64489 = 3259854461 -- Steps: 176934
# Crown Sterling: 64489 * 50549 = 3259854461 -- Steps: 578599
# --------------------------------------------------------------------------------------------------
# Challenge 83: Factor 3356548093 | Solution: 63659 * 52727 (not shown to contestants)
# Trial division: 52727 * 63659 = 3356548093 -- Steps: 184557
# Crown Sterling: 52727 * 63659 = 3356548093 -- Steps: 260209
# --------------------------------------------------------------------------------------------------
# Challenge 84: Factor 2788344683 | Solution: 45553 * 61211 (not shown to contestants)
# Trial division: 45553 * 61211 = 2788344683 -- Steps: 159448
# Crown Sterling: 61211 * 45553 = 2788344683 -- Steps: 79141
# --------------------------------------------------------------------------------------------------
# Challenge 85: Factor 1854292681 | Solution: 51421 * 36061 (not shown to contestants)
# Trial division: 36061 * 51421 = 1854292681 -- Steps: 126226
# Crown Sterling: 36061 * 51421 = 1854292681 -- Steps: 356919
# --------------------------------------------------------------------------------------------------
# Challenge 86: Factor 2766149039 | Solution: 56659 * 48821 (not shown to contestants)
# Trial division: 48821 * 56659 = 2766149039 -- Steps: 170886
# Crown Sterling: 48821 * 56659 = 2766149039 -- Steps: 428597
# --------------------------------------------------------------------------------------------------
# Challenge 87: Factor 1313844109 | Solution: 36217 * 36277 (not shown to contestants)
# Trial division: 36217 * 36277 = 1313844109 -- Steps: 126772
# Crown Sterling: 36217 * 36277 = 1313844109 -- Steps: 9279
# --------------------------------------------------------------------------------------------------
# Challenge 88: Factor 1765544453 | Solution: 35023 * 50411 (not shown to contestants)
# Trial division: 35023 * 50411 = 1765544453 -- Steps: 122593
# Crown Sterling: 35023 * 50411 = 1765544453 -- Steps: 2721759
# --------------------------------------------------------------------------------------------------
# Challenge 89: Factor 1283210059 | Solution: 35897 * 35747 (not shown to contestants)
# Trial division: 35747 * 35897 = 1283210059 -- Steps: 125127
# Crown Sterling: 35747 * 35897 = 1283210059 -- Steps: 1096843
# --------------------------------------------------------------------------------------------------
# Challenge 90: Factor 2120597719 | Solution: 43579 * 48661 (not shown to contestants)
# Trial division: 43579 * 48661 = 2120597719 -- Steps: 152539
# Crown Sterling: 43579 * 48661 = 2120597719 -- Steps: 1632781
# --------------------------------------------------------------------------------------------------
# Challenge 91: Factor 2150090737 | Solution: 55439 * 38783 (not shown to contestants)
# Trial division: 38783 * 55439 = 2150090737 -- Steps: 135753
# Crown Sterling: 38783 * 55439 = 2150090737 -- Steps: 971721
# --------------------------------------------------------------------------------------------------
# Challenge 92: Factor 2393270441 | Solution: 62903 * 38047 (not shown to contestants)
# Trial division: 38047 * 62903 = 2393270441 -- Steps: 133177
# Crown Sterling: 62903 * 38047 = 2393270441 -- Steps: 122913
# --------------------------------------------------------------------------------------------------
# Challenge 93: Factor 3768467251 | Solution: 65033 * 57947 (not shown to contestants)
# Trial division: 57947 * 65033 = 3768467251 -- Steps: 202827
# Crown Sterling: 65033 * 57947 = 3768467251 -- Steps: 1673819
# --------------------------------------------------------------------------------------------------
# Challenge 94: Factor 2878745479 | Solution: 59699 * 48221 (not shown to contestants)
# Trial division: 48221 * 59699 = 2878745479 -- Steps: 168786
# Crown Sterling: 48221 * 59699 = 2878745479 -- Steps: 421719
# --------------------------------------------------------------------------------------------------
# Challenge 95: Factor 2556480029 | Solution: 63463 * 40283 (not shown to contestants)
# Trial division: 40283 * 63463 = 2556480029 -- Steps: 141003
# Crown Sterling: 40283 * 63463 = 2556480029 -- Steps: 2224567
# --------------------------------------------------------------------------------------------------
# Challenge 96: Factor 1444663379 | Solution: 38321 * 37699 (not shown to contestants)
# Trial division: 37699 * 38321 = 1444663379 -- Steps: 131959
# Crown Sterling: 37699 * 38321 = 1444663379 -- Steps: 763679
# --------------------------------------------------------------------------------------------------
# Challenge 97: Factor 3199225619 | Solution: 56377 * 56747 (not shown to contestants)
# Trial division: 56377 * 56747 = 3199225619 -- Steps: 197332
# Crown Sterling: 56747 * 56377 = 3199225619 -- Steps: 927065
# --------------------------------------------------------------------------------------------------
# Challenge 98: Factor 1847886133 | Solution: 41519 * 44507 (not shown to contestants)
# Trial division: 41519 * 44507 = 1847886133 -- Steps: 145329
# Crown Sterling: 41519 * 44507 = 1847886133 -- Steps: 265319
# --------------------------------------------------------------------------------------------------
# Challenge 99: Factor 2687103857 | Solution: 47143 * 56999 (not shown to contestants)
# Trial division: 47143 * 56999 = 2687103857 -- Steps: 165013
# Crown Sterling: 56999 * 47143 = 2687103857 -- Steps: 1632249
# --------------------------------------------------------------------------------------------------
# Challenge 100: Factor 1784140499 | Solution: 53101 * 33599 (not shown to contestants)
# Trial division: 33599 * 53101 = 1784140499 -- Steps: 117609
# Crown Sterling: 53101 * 33599 = 1784140499 -- Steps: 170663
# --------------------------------------------------------------------------------------------------
# After 100 games played with 32-bit RSA public keys, on average, the Crown Sterling
# Reciprocal Factoring method was 5.85 times slower than trial division (brute force).
#
# Process finished with exit code 0
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment