Puzzle: Factor these 256-bit semiprimes

Question

Challenge

Write a program to factor this set of 10 numbers:

15683499351193564659087946928346254200387478295674004601169717908835380854917
24336606644769176324903078146386725856136578588745270315310278603961263491677
39755798612593330363515033768510977798534810965257249856505320177501370210341
45956007409701555500308213076326847244392474672803754232123628738514180025797
56750561765380426511927268981399041209973784855914649851851872005717216649851
64305356095578257847945249846113079683233332281480076038577811506478735772917
72232745851737657087578202276146803955517234009862217795158516719268257918161
80396068174823246821470041884501608488208032185938027007215075377038829809859
93898867938957957723894669598282066663807700699724611406694487559911505370789
99944277286356423266080003813695961952369626021807452112627990138859887645249

Each of these:

• Is a 77-digit number less than 2^256.
• Is a semiprime (e.g., the product of exactly 2 primes).
• Has something in common with at least one other number in the set.

Thus, this challenge is not about general factoring of 256-bit semiprimes, but about factoring these semiprimes. It is a puzzle. There is a trick. The trick is fun.

It is possible to factor each of these numbers with surprising efficiency. Therefore, the algorithm you choose will make a much bigger difference than the hardware you use.

Rules

1. This is code-golf, so the shortest answer wins.
2. You may use any method of factoring. (But don't precompute the answers and just print them. You program should do actual work.)
3. You may use any programming language (or combination of languages), and any libraries they provide or you have installed. However, you probably won't need anything fancy.

Answer 1

Pyth, 12 bytes

V.Q--iRN.Q1N

Try it here: Demonstration

Explanation:

               implicit: .Q is the list of the input numbers
V.Q            for N in .Q:
     iRN.Q        compute the gcd of N with each number in .Q
    -     1       remove 1s
   -       N      remove the number N and print

Answer 2

Julia

f=l->(A=map(big,[gcd(l[i],l[j]) for i=1:length(l),j=1:length(l)]);A-=eye(A).*(l-1);for i=1:length(l) println(l[i]," = ",join(unique(A[i,:])," × "))end);

Running it:

julia> tic();f(l);toc()
15683499351193564659087946928346254200387478295674004601169717908835380854917 = 1 × 123830525223423718982054269884856893727 × 126652934104061135988638942588043498971
24336606644769176324903078146386725856136578588745270315310278603961263491677 = 123830525223423718982054269884856893727 × 1 × 196531562802139162910711939551924590851
39755798612593330363515033768510977798534810965257249856505320177501370210341 = 126652934104061135988638942588043498971 × 1 × 313895598975456800331958744266933545471
45956007409701555500308213076326847244392474672803754232123628738514180025797 = 1 × 196531562802139162910711939551924590851 × 233835251470362519313085185758275325847
56750561765380426511927268981399041209973784855914649851851872005717216649851 = 1 × 218051709768607497734800854124975705007 × 260261943488556401874345256435550440693
64305356095578257847945249846113079683233332281480076038577811506478735772917 = 1 × 218051709768607497734800854124975705007 × 294908745103709254641398276907437631131
72232745851737657087578202276146803955517234009862217795158516719268257918161 = 1 × 233835251470362519313085185758275325847 × 308904433345854212511531098349325333463
80396068174823246821470041884501608488208032185938027007215075377038829809859 = 1 × 260261943488556401874345256435550440693 × 308904433345854212511531098349325333463
93898867938957957723894669598282066663807700699724611406694487559911505370789 = 1 × 294908745103709254641398276907437631131 × 318399740590727338211743341325021840319
99944277286356423266080003813695961952369626021807452112627990138859887645249 = 1 × 313895598975456800331958744266933545471 × 318399740590727338211743341325021840319
elapsed time: 0.002534739 seconds

Note: Because of how Julia operates, you might want to run it twice - the first time you run it, the tic/toc will include the time required to "compile" it. The second time, it will have already compiled it.

Answer 3

CJam, 32 bytes

q~]__ff{{_@\%}h}:|1-_m*_::*\er:p

Try it online: permalink for Chrome | permalink for Firefox

Answer 4

CJam, 38 bytes

q~]_2m*{~{_@\%}h;}%_2$-&2m*f{_::*@#=p}

Try it here.

This answer is shorter than any of the factors in the output.

Answer 5

J, 2 bytes

This is code-golf now, so I assume efficiency doesn't actually matter, which means:

q:

(J's "factor prime" function) will return the right answer (in the form of a neatly formatted 2x10 array!) if you pass it an array of bignums give it a couple of hours/days to factor the semiprimes.

Answer 6

Pyth, 15 13 12 bytes

jbmS{iLd.Q.Q

Expects the list of primes seperated by newlines on stdin. Outputs in the following format:

[1, 123830525223423718982054269884856893727, 126652934104061135988638942588043498971, 15683499351193564659087946928346254200387478295674004601169717908835380854917]
[1, 123830525223423718982054269884856893727, 196531562802139162910711939551924590851, 24336606644769176324903078146386725856136578588745270315310278603961263491677]
[1, 126652934104061135988638942588043498971, 313895598975456800331958744266933545471, 39755798612593330363515033768510977798534810965257249856505320177501370210341]
[1, 196531562802139162910711939551924590851, 233835251470362519313085185758275325847, 45956007409701555500308213076326847244392474672803754232123628738514180025797]
[1, 218051709768607497734800854124975705007, 260261943488556401874345256435550440693, 56750561765380426511927268981399041209973784855914649851851872005717216649851]
[1, 218051709768607497734800854124975705007, 294908745103709254641398276907437631131, 64305356095578257847945249846113079683233332281480076038577811506478735772917]
[1, 233835251470362519313085185758275325847, 308904433345854212511531098349325333463, 72232745851737657087578202276146803955517234009862217795158516719268257918161]
[1, 260261943488556401874345256435550440693, 308904433345854212511531098349325333463, 80396068174823246821470041884501608488208032185938027007215075377038829809859]
[1, 294908745103709254641398276907437631131, 318399740590727338211743341325021840319, 93898867938957957723894669598282066663807700699724611406694487559911505370789]
[1, 313895598975456800331958744266933545471, 318399740590727338211743341325021840319, 99944277286356423266080003813695961952369626021807452112627990138859887645249]

Answer 7

Pyth, 4 bytes

Since we don't have to abuse the common divisors we can simply use the factorization function and map it to the input:

PM.Q

Yay loopholes!