Ponder This Challenge - April 2017 - Factoring

Ponder This Challenge:

IBM recently announced a commercial Quantum computer. Such a computer can factor large numbers, using a Shor algorithm.

The challenge this month is to factor at least one of the following three numbers:

1. 27771495424394652906650011597233066116343506387184320546233728271726480989807112498372640545334956743914011373
2. 98296593067163321549931012857525979998165090637663230976866143160359417516252340928637985390415053795128313
3. 1412534667091752138605679066750993949837793629454397369052717798704788621599573184763086599428517731585079

Bonus '*' if you factor all three.

Update (10/4): Hint: The challenge is solvable in seconds of CPU time. The Bonus requires some creative view, but can be solved in seconds too.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  Many of you used factoring programs. Some of the solvers didn't even notice that two has a common factor.
  We meant you to solve it using the GCD algorithm on all pairs, thereby discovering a common factor, and then reading the factors as ASCII strings:

  The factorization of the three numbers is as follows:

  n1 = 1013209076077649209484940814946799145391416348710836269949 *
  27409442019512990822647850170314237623576356233289777
     = ')Reverse the characters}' * 'IBM Quantum computer 1'

  n2 = 1013209076077649209484940814946799145391416348710836269949 *
  97015113058097176690586226108597571924676074369837
     = ')Reverse the characters}' * 'Bad printable primes-'

  The common factor is a hint: reversing the string we get a factor of the third number
  n3 = 3076048694171659720381726519691214280505664619002804392489 *
  459204260897478908239259636478617449777306089311
     = '}sretcarahc eht esreveR)' * 'PonderThis Apr 2017_'

  Armin Krauß was the first to send us the ASCII strings and got a second '**' for that.

Solvers

• Reiner Martin (27/03/2017 03:15 PM IDT)
• *Robert Gerbicz (27/03/2017 04:43 PM IDT)
• *Benjamin Buhrow (27/03/2017 06:49 PM IDT)
• Bert Dobbelaere (27/03/2017 08:39 PM IDT)
• *Serge Batalov (28/03/2017 12:24 AM IDT)
• George Barnett (28/03/2017 09:53 AM IDT)
• *Tom Womack (28/03/2017 12:44 PM IDT)
• *Mike Vang (28/03/2017 02:30 PM IDT)
• Andreas Stiller (28/03/2017 06:51 PM IDT)
• Raymond Lo (28/03/2017 07:23 PM IDT)
• JJ Rabeyrin (29/03/2017 02:38 AM IDT)
• David Owen (29/03/2017 04:45 AM IDT)
• Serge-Gautier (29/03/2017 05:05 PM IDT)
• Yan-Wu He (29/03/2017 10:38 PM IDT)
• *Stéphane Higueret (30/03/2017 09:19 AM IDT)
• Yoav Kaempfer (30/03/2017 11:52 AM IDT)
• *Anatoly Vorobey (30/03/2017 12:02 AM IDT)
• *Andreas Höglund (30/03/2017 02:51 PM IDT)
• *David F.H. Dunkley (30/03/2017 08:40 PM IDT)
• *Michael Liepelt (31/03/2017 09:55 AM IDT)
• Joaquim Neves Carrapa (31/03/2017 05:31 PM IDT)
• Kurt Foster (31/03/2017 11:13 PM IDT)
• *Sergey Koposov (02/04/2017 02:14 AM IDT)
• Shirish Chinchalkar (02/04/2017 07:21 PM IDT)
• *Robert Franke (02/04/2017 09:45 PM IDT)
• *Oleg Vlasii (03/04/2017 01:16 AM IDT)
• *Chris Shannon (03/04/2017 09:27 AM IDT)
• *Yan-Wu He (03/04/2017 06:20 PM IDT)
• *Leonid Kalmankin (03/04/2017 08:40 PM IDT)
• Steven Langerwerf (04/04/2017 09:55 AM IDT)
• *Vladimir M. Milovanović (04/04/2017 10:27 AM IDT)
• Benjamin Lui (04/04/2017 02:07 PM IDT)
• *Don Leclair (04/04/2017 02:20 PM IDT)
• *Daniëlle van den Berg (05/04/2017 12:18 AM IDT)
• *Antonio García Astudillo (05/04/2017 12:45 AM IDT)
• Mathias Schenker (05/04/2017 03:36 AM IDT)
• *Alexander Chetverin (05/04/2017 06:32 AM IDT)
• *Hugo Pfoertner (05/04/2017 06:38 AM IDT)
• *David Greer (05/04/2017 09:37 AM IDT)
• *Maksym Voznyy (05/04/2017 01:15 PM IDT)
• *mathias schenker (05/04/2017 07:12 PM IDT)
• *Sergey Shashkov (05/04/2017 07:35 PM IDT)
• *Teake Nutma (05/04/2017 08:48 PM IDT)
• *Rich Smith (06/04/2017 03:13 AM IDT)
• Andreas Knüpfer (06/04/2017 04:46 PM IDT)
• *Tihomir Mescic (08/04/2017 09:48 AM IDT)
• *Karoly Csalogany (09/04/2017 09:27 PM IDT)
• Lamkaddem Abdellah (11/04/2017 02:11 PM IDT)
• *Tamir Ganor & Shouky Dan (11/04/2017 02:21 PM IDT)
• Michael J Swart (12/04/2017 05:56 PM IDT)
• Evert van Dijken (13/04/2017 11:54 AM IDT)
• **Armin Krauß (13/04/2017 09:58 PM IDT)
• Arthur Vause (14/04/2017 04:02 PM IDT)
• Amer Hashem Alkahtani (14/04/2017 11:45 PM IDT)
• Tomoyuki Iwase (17/04/2017 12:18 PM IDT)
• Anders Bisbjerg Madsen (17/04/2017 10:09 PM IDT)
• Michael Rosola (18/04/2017 04:13 PM IDT)
• Dmitry Kim (19/04/2017 03:32 AM IDT)
• *Elias Papavassilopoulos (19/04/2017 12:11 PM IDT)
• *Tyler Mullen (22/04/2017 01:18 PM IDT)
• *Jörg Binder (23/04/2017 08:25 PM IDT)
• Asaf Aharoni (23/04/2017 11:21 PM IDT)
• Zilin Jiang (24/04/2017 11:18 AM IDT)
• *Alper Halbutogullari (24/04/2017 06:17 PM IDT)
• Guy Danielli (26/04/2017 01:07 PM IDT)
• Hyung Sik Hwang (27/04/2017 11:25 AM IDT)
• Clive Tong (27/04/2017 11:54 AM IDT)
• Jan Fricke (27/04/2017 01:28 PM IDT)
• Thomas Egense (28/04/2017 12:09 PM IDT)
• Daniel Azzopardi (29/04/2017 11:15 AM IDT)
• *Rickard Björklund (29/04/2017 08:04 PM IDT)
• *Kang Jin Cho (30/04/2017 12:44 PM IDT)
• Satendra Mani Tiwari (30/04/2017 10:28 PM IDT)
• Alexander Korshkov (30/04/2017 11:23 PM IDT)
• *Oscar Volpatti (01/05/2017 04:40 PM IDT)
• Hanlin Ren (01/05/2017 05:18 PM IDT)