Who changed the subject?

[Res Ipsa]

Most current encryption algorithms employ very large pseudo prime numbers as an element of their key.

https://www.johndcook.com/blog/2018/12/ ... udoprimes/

Very interesting!

Someone just changed the title from "Hacking" to "Factorizing large numbers".

Can you please explain to the mods what Hacking is . There's no need for them to get scared.

Shoot the boss a PM.

[Gadianton]

turned out to be a funner subject than I thought. So what constitutes cheating, DT? is hacking good or bad?

you should learn python. download something like pycharm and do a couple simple tutorials. then just explore the options.

here's a quick and dirty method:

Code: Select all

c = 970
i = 1
a = []
g = []
while i < c:
    i += 1
    if c / i == int(c / i):
        a.append(int(c / i))

for b in a:
    for d in a:
        if b*d == c:
            g.append((b,d))

g = list(set(g))

print(g)

[(5, 194), (97, 10), (10, 97), (2, 485), (485, 2), (194, 5)]

So this is just going to divide your number by every number up to itself and if the result is an integer, it saves the number. Then it multiplies the list of those saved numbers by each other and saves the ones that equal your number. Your example is a special case where there is only one solution.

Anyway, this works in theory, but as the number gets bigger and bigger, it takes longer and longer to calculate, so I can wait for minutes or hours, or try to improve performance.

I'm counting every number, but there's a lot of redundancy because if my input isn't divisible by 2, then it's not divisible by 4 or 6 or 8, right? So I'm potentially trying tens of thousands of numbers that we know before the fact don't work. So we need only unique number that aren't divisible by --- so what Steelhead and Chap said. I need a prime number generator, but since that's going to be calculation intensive by brute force and I don't want to try for a nobel prize right now, I'm going to create a lot of prime numbers and save as a cache file.

Code: Select all

c = 10000000

#4, 25, 168, 1229, 9592, 78498, 664579
path = "c:/scriptstuff"
np = []
all = [i for i in range(2, c)]

for i in range(2, c):
    for j in range(2, c):
        num = i * j
        if num < c:
            np.append(num)
        else:
            break

primes = set(all) - set(np)
print(len(primes))

primes = list(primes)
primes.sort()

with open(path + '/fact', 'w') as f:
    for p in primes:
        f.write(str(p) + '\n')

make a list of every number from 1 to my maximum big number, set that aside. Then recursively multiply integers together-- 1 x 2, 2 x 2, 2 x 3 etc, but stop once we reach the defined big number. If I can generate a number by multiplication this way, I know it's not a prime. So subtract the list of NOT-PRIME numbers from the list of ALL numbers, and that gives all the prime numbers and save that to a file.

At the top I have a list of numbers following # -- 4, 25 etc. That's the number of primes generated every time I increase the target number by factor of 10. I did that to estimate performance -- how intensive is it going to be to read a large cache file? It took a couple minutes to generate 664k + primes, but that's not bad to read in. Also, I know that you're just interested in a special case numbers where you're squaring big numbers into huge numbers, so that makes it easier. You would need to use python or something to work out a more creative way to increase calculation time to discourage cheating.

Code: Select all

path = "c:/scriptstuff"

f_this = 37562422334761

with open(path + '/fact') as f:
    primes = f.readlines()

#print(primes)
primes = [int(p) for p in primes]

fac = []
for p in primes:
    if p < f_this:
        if f_this / p == int(f_this / p):
            fac.append(p)
    else:
        break
print(fac)

So the final script reads the cache in, and then uses the previous logic of dividing our big number by another number that increments and saves if it produces and integer, but now it's counting primes so skipping the redundancies and finds your answers nearly instantly.

[doubtingthomas]

turned out to be a funner subject than I thought. So what constitutes cheating, DT? is hacking good or bad?

you should learn python. download something like pycharm and do a couple simple tutorials. then just explore the options.

here's a quick and dirty method:

Nice!

What's your proficiency level on Python? and how many languages do you know?