Easy one for people with quantum computers

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Easy one for people with quantum computers

Postby Cosmologicon » Thu Aug 30, 2007 10:10 pm UTC

What's the largest one-digit (less than 10) divisor of the difference between the two prime factors of this number?

Code: Select all

104913711085781896126454770340755788732981853849187266431122452452451390
280973458025461551845569899386779611472062205932422918564054633271910624
890874936424056872865892700892147170039730774083890007034451970570029418
6612157351983601

User avatar
notzeb
Without Warning
Posts: 629
Joined: Thu Mar 08, 2007 5:44 am UTC
Location: a series of tubes

Postby notzeb » Thu Aug 30, 2007 10:21 pm UTC

I can tell you with absolute certainty that the answer isn't three (because according to bc that ridiculous number is congruent to two mod three).

Two definitely divides the difference of the primes.

Edit: sadly, that is congruent to a square mod each of 5, 7, and 8. I need a new method...

Edit2: THE ANSWER IS 8! This is because the answer can't be 9 (since 3 doesn't divide the difference), and because 8 must divide the difference, since x*y = 1 (mod 8 ) iff x = y (mod 8 ) and x = 1 (mod 2).


Remember your spoilers please.
Zµ«V­jÕ«ZµjÖ­Zµ«VµjÕ­ZµkV­ZÕ«VµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­ZµkV­ZÕ«VµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­ZµkV­ZÕ«ZµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­Z

deja
Posts: 35
Joined: Sat Aug 25, 2007 10:36 pm UTC

Postby deja » Thu Aug 30, 2007 11:17 pm UTC

how did you do that? as in, how did you find the prime factors?
Vu?

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Postby Cosmologicon » Fri Aug 31, 2007 12:14 am UTC

Well done, notzeb. Now for a slightly harder one. Same question, but for the number:

Code: Select all

35544461252364521866307838704858741747465998947350920506605608383897
50701395270999760991533951978698872252958747747098478165938801532525
66053087405410897890681299705997094443537778877126935681849185311894
797235279872431379

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

Postby Cauchy » Fri Aug 31, 2007 1:17 am UTC

partial solution wrote:
The number is congruent to 3 mod 4, so of the prime factors, one is 1 mod 4 and one is 3 mod 4, so their difference is 2 mod 4 and hence has exactly one factor of 2.

The number is congruent to 7 mod 9, so the prime factors are either 1 and 7 mod 9, 2 and 8 mod 9, 4 and 4 mod 9, or 5 and 5 mod 9. The difference, then, is either 6 or 0 mod 9, so it has at least one factor of 3 and possibly two or more.

The number is congruent to 2 mod 7, so the prime factors are either 1 and 2 mod 7, 3 and 3 mod 7, 4 and 4 mod 7, or 5 and 6 mod 7. The difference, then, is either 1 or 0 mod 7, so it might have a factor of 7 and it might not.

The largest one-digit factor is 9 if the difference has two or more factors of 3, 7 if that's not true but it has a factor of 7, and 6 otherwise.


User avatar
Mouffles
Posts: 60
Joined: Fri Jul 06, 2007 10:02 am UTC
Location: New Zealand

Postby Mouffles » Sat Sep 01, 2007 1:06 am UTC

solution wrote:Wait... this number has a small factor. It's divisible by 101. The answer is 7.
I'm not sure how to do it without factorising it, though.
EDIT: although knowing that 101 is a factor you can find the answer from what Cauchy wrote.
In the spirit of taking things too far - the 5x5x5x5x5 Rubik's Cube.

User avatar
notzeb
Without Warning
Posts: 629
Joined: Thu Mar 08, 2007 5:44 am UTC
Location: a series of tubes

Postby notzeb » Sat Sep 01, 2007 5:01 am UTC

and there I was testing prime factors up to 37...

Then I stop and say, "no, he'd never do something silly like that. And if he did, he'd make it a prime less than 40"... ...
Zµ«V­jÕ«ZµjÖ­Zµ«VµjÕ­ZµkV­ZÕ«VµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­ZµkV­ZÕ«VµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­ZµkV­ZÕ«ZµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­Z

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Postby Cosmologicon » Wed Sep 05, 2007 8:06 pm UTC

Right. Well done. How about this:

Code: Select all

56687714862667575812327835726382791321590348765538134310085932576648
13712106224942547269598016885791503920385800385769350708154875013699
07289477586318867381203257635679136384237963287393888359827202905375
59823

Quan
Posts: 71
Joined: Mon Aug 20, 2007 6:17 pm UTC
Location: Manchester, UK

Postby Quan » Thu Sep 06, 2007 2:26 am UTC

solution wrote:2


:) , factoring numbers like that is easy :P
I'm so geeky I got really excited about making this signature in SVG until it occurred to me HTML would obviously be turned off ¬_¬'

User avatar
Mouffles
Posts: 60
Joined: Fri Jul 06, 2007 10:02 am UTC
Location: New Zealand

Postby Mouffles » Thu Sep 06, 2007 3:27 am UTC

Come on... at least make the numbers big enough so they require a quantum computer to factorise!
In the spirit of taking things too far - the 5x5x5x5x5 Rubik's Cube.

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Postby Cosmologicon » Thu Sep 06, 2007 3:59 am UTC

Er... how big is that these days? 200 digits was typical for an example back when I first learned about this stuff. How fast can that be factored now?

User avatar
Mouffles
Posts: 60
Joined: Fri Jul 06, 2007 10:02 am UTC
Location: New Zealand

Postby Mouffles » Thu Sep 06, 2007 4:28 am UTC

200 digits still takes a while, in general. But your two primes were twin primes, which made it very quick to factorise.
In the spirit of taking things too far - the 5x5x5x5x5 Rubik's Cube.

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Postby Cosmologicon » Thu Sep 06, 2007 4:36 am UTC

Well, obviously if you know they're twin primes it's easy, but that's the whole point! Or are you saying that a standard factoring algorithm will pick that out? I admit I'm not familiar with standard algorithms.

Note that a quantum computer wouldn't really help with any of the three I've posted. I just titled the thread that to throw you off track. Do you want one that's actually difficult to factor and you can't figure out by some other means? I can oblige, but I don't know how much fun that would be!

User avatar
Nimz
Posts: 580
Joined: Thu Aug 02, 2007 9:49 am UTC
Location: the origin

Postby Nimz » Thu Sep 06, 2007 7:43 am UTC

I would imagine twin primes would be easier for an algorithm to find, especially if the algorithm starts by looking for the square root of the number to be factored and works its way down from there.

Being more comfortable with small numbers, my initial method of looking for factors would be the reverse - still find the square root first, but then work my way up to that point. It would probably be simpler to implement a "work your way down" approach into a program, though.
LOWA

User avatar
Mouffles
Posts: 60
Joined: Fri Jul 06, 2007 10:02 am UTC
Location: New Zealand

Postby Mouffles » Thu Sep 06, 2007 7:58 am UTC

I factored the number in GAP using the FactInt package. You can set it to tell you what steps it is taking. It starts out by checking whether n=b^k +- 1, so it immediately found the twin prime factors. (It then checks all primes <1000, then moves on to more complicated algorithms)
In the spirit of taking things too far - the 5x5x5x5x5 Rubik's Cube.

Quan
Posts: 71
Joined: Mon Aug 20, 2007 6:17 pm UTC
Location: Manchester, UK

Postby Quan » Thu Sep 06, 2007 2:01 pm UTC

200 digits is pretty much impossible with a standard computer if you observe some basic rules, those rules imposing the general idea of these 2 points:

1. Not too close to the square root so that an algorithm working from the square root out can easily find them
2. Not too far apart so the smaller prime number becomes a weak target.

I had a class in my first year of my degree where we had to crack each others encryption, where we gave out the public key pq with an encoded message and we had to crack it by finding p and q.

Back then anyone with a pq > about 105, I couldn't crack unless their numbers broke 1 of the 2 rules above. Or this 1 case where it was rather easy to crack because the number started with a 1, had about 70 0's following it, followed by about 7 random numbers, followed by about another 70 0's followed by about 14 random numbers or so.

I was using a 2.6 GHz Celeron to crack them from my laptop, these days I have a much faster CPU, but no idea how much of a difference that'd make on my ability to crack them.
I'm so geeky I got really excited about making this signature in SVG until it occurred to me HTML would obviously be turned off ¬_¬'

User avatar
Pesto
Posts: 737
Joined: Wed Sep 05, 2007 5:33 pm UTC
Location: Berkeley, CA

Postby Pesto » Thu Sep 06, 2007 3:22 pm UTC

Nimz wrote:Being more comfortable with small numbers, my initial method of looking for factors would be the reverse - still find the square root first, but then work my way up to that point. It would probably be simpler to implement a "work your way down" approach into a program, though.

Using this approach, finding the square root would be irrelevant. If you're checking from 2 on up sequentially, you'll find a factor before you ever get to the square root. The point of using the square root is so that you have a defined range to do more complex things within.

User avatar
bitwiseshiftleft
Posts: 295
Joined: Tue Jan 09, 2007 9:07 am UTC
Location: Stanford
Contact:

Postby bitwiseshiftleft » Wed Sep 12, 2007 5:16 am UTC

Quan wrote:200 digits is pretty much impossible with a standard computer...


According to Wikipedia, the current factoring record (set ~2 years ago) for products of random primes is 200 digits. It took several months on an 80-way Opteron cluster.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 9 guests