## Easy one for people with quantum computers

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

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

### Easy one for people with quantum computers

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

Code: Select all

`1049137110857818961264547703407557887329818538491872664311224524524513902809734580254615518455698993867796114720622059324229185640546332719106248908749364240568728658927008921471700397307740838900070344519705700294186612157351983601`

notzeb
Without Warning
Posts: 629
Joined: Thu Mar 08, 2007 5:44 am UTC
Location: a series of tubes
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).

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
how did you do that? as in, how did you find the prime factors?
Vu?

Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:
Well done, notzeb. Now for a slightly harder one. Same question, but for the number:

Code: Select all

`355444612523645218663078387048587417474659989473509205066056083838975070139527099976099153395197869887225295874774709847816593880153252566053087405410897890681299705997094443537778877126935681849185311894797235279872431379`

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm 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.

Mouffles
Posts: 60
Joined: Fri Jul 06, 2007 10:02 am UTC
Location: New Zealand
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.

notzeb
Without Warning
Posts: 629
Joined: Thu Mar 08, 2007 5:44 am UTC
Location: a series of tubes
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

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

Code: Select all

`56687714862667575812327835726382791321590348765538134310085932576648137121062249425472695980168857915039203858003857693507081548750136990728947758631886738120325763567913638423796328739388835982720290537559823`

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

, factoring numbers like that is easy
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 ¬_¬'

Mouffles
Posts: 60
Joined: Fri Jul 06, 2007 10:02 am UTC
Location: New Zealand
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.

Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:
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?

Mouffles
Posts: 60
Joined: Fri Jul 06, 2007 10:02 am UTC
Location: New Zealand
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.

Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:
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!

Nimz
Posts: 580
Joined: Thu Aug 02, 2007 9:49 am UTC
Location: the origin
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

Mouffles
Posts: 60
Joined: Fri Jul 06, 2007 10:02 am UTC
Location: New Zealand
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
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 ¬_¬'

Pesto
Posts: 737
Joined: Wed Sep 05, 2007 5:33 pm UTC
Location: Berkeley, CA
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.

bitwiseshiftleft
Posts: 295
Joined: Tue Jan 09, 2007 9:07 am UTC
Location: Stanford
Contact:
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.