mersenneforum.org April 2017
 Register FAQ Search Today's Posts Mark Forums Read

2017-05-04, 03:03   #23
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

2·17·59 Posts

Quote:
 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
As stated, that gives gibberish, neither numbers nor factors.
Try it here:

http://www.unit-conversion.info/texttools/ascii/

Last fiddled with by a1call on 2017-05-04 at 03:04

 2017-05-04, 05:09 #24 Harrywill   "Harry Willam" May 2017 USA 22·5 Posts Math Puzzles Questions If R is denoted by 8, G by 4, I by 2, A by 7, N by 3 ,H by 1,and S by 0 then what will be the numeric form of the word GARNISH when written in the reverse order?
2017-05-04, 15:26   #25
Dr Sardonicus

Feb 2017
Nowhere

5×19×47 Posts

Quote:
Originally Posted by a1call
Quote:
 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
As stated, that gives gibberish, neither numbers nor factors.
It took me a few minutes to figure out what was going on. A major clue was how much shorter the messages were than the numbers.

The conversion to ASCII is accomplished via converting decimal numbers to base 256.

Here is that conversion, carried out using a PARI-GP script, on the common factor of the first two challenge numbers. It gives the base-256 digits in reverse order, of course.

? n=1013209076077649209484940814946799145391416348710836269949;

m=n;i=0;until(m==0,r=m%256;m=m\256;print("256^",i," digit in decimal ",r," Converted to ASCII ",Strchr(r));i++)

256^0 digit in decimal 125 Converted to ASCII }
256^1 digit in decimal 115 Converted to ASCII s
256^2 digit in decimal 114 Converted to ASCII r
256^3 digit in decimal 101 Converted to ASCII e
256^4 digit in decimal 116 Converted to ASCII t
256^5 digit in decimal 99 Converted to ASCII c
256^6 digit in decimal 97 Converted to ASCII a
256^7 digit in decimal 114 Converted to ASCII r
256^8 digit in decimal 97 Converted to ASCII a
256^9 digit in decimal 104 Converted to ASCII h
256^10 digit in decimal 99 Converted to ASCII c
256^11 digit in decimal 32 Converted to ASCII
256^12 digit in decimal 101 Converted to ASCII e
256^13 digit in decimal 104 Converted to ASCII h
256^14 digit in decimal 116 Converted to ASCII t
256^15 digit in decimal 32 Converted to ASCII
256^16 digit in decimal 101 Converted to ASCII e
256^17 digit in decimal 115 Converted to ASCII s
256^18 digit in decimal 114 Converted to ASCII r
256^19 digit in decimal 101 Converted to ASCII e
256^20 digit in decimal 118 Converted to ASCII v
256^21 digit in decimal 101 Converted to ASCII e
256^22 digit in decimal 82 Converted to ASCII R
256^23 digit in decimal 41 Converted to ASCII )

 2017-05-04, 17:25 #26 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 7D616 Posts Thank you very much Dr S. It took me a few minutes to figure out what you were saying. But of course I am still completely lost. How can anyone figure that out without being a psychic? How does that convert to a common factor with the 3rd number?
2017-05-04, 20:55   #27
Dr Sardonicus

Feb 2017
Nowhere

5×19×47 Posts

Quote:
 Originally Posted by a1call Thank you very much Dr S. How does that convert to a common factor with the 3rd number?
The desired factor is obtained by reversing the digits of base-256 representation of n. I have modified my script to include this computation.

? n=1013209076077649209484940814946799145391416348710836269949;

revn=0;m=n;i=0;until(m==0,r=m%256;m=m\256;print("256^",i," digit in decimal ",r," Converted to ASCII ",Strchr(r));i++;revn=256*revn+r);print(revn)

256^0 digit in decimal 125 Converted to ASCII }
256^1 digit in decimal 115 Converted to ASCII s
256^2 digit in decimal 114 Converted to ASCII r
256^3 digit in decimal 101 Converted to ASCII e
256^4 digit in decimal 116 Converted to ASCII t
256^5 digit in decimal 99 Converted to ASCII c
256^6 digit in decimal 97 Converted to ASCII a
256^7 digit in decimal 114 Converted to ASCII r
256^8 digit in decimal 97 Converted to ASCII a
256^9 digit in decimal 104 Converted to ASCII h
256^10 digit in decimal 99 Converted to ASCII c
256^11 digit in decimal 32 Converted to ASCII
256^12 digit in decimal 101 Converted to ASCII e
256^13 digit in decimal 104 Converted to ASCII h
256^14 digit in decimal 116 Converted to ASCII t
256^15 digit in decimal 32 Converted to ASCII
256^16 digit in decimal 101 Converted to ASCII e
256^17 digit in decimal 115 Converted to ASCII s
256^18 digit in decimal 114 Converted to ASCII r
256^19 digit in decimal 101 Converted to ASCII e
256^20 digit in decimal 118 Converted to ASCII v
256^21 digit in decimal 101 Converted to ASCII e
256^22 digit in decimal 82 Converted to ASCII R
256^23 digit in decimal 41 Converted to ASCII )
3076048694171659720381726519691214280505664619002804392489

 2017-05-04, 22:32 #28 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2·17·59 Posts Very impressive, thank you so much.
 2017-05-05, 08:00 #30 R. Gerbicz     "Robert Gerbicz" Oct 2005 Hungary 2·36 Posts For a real world example of the puzzle see the 7-th page of https://smartfacts.cr.yp.to/smartfacts-20130916.pdf (batch gcd).
2017-05-05, 13:45   #31
Dr Sardonicus

Feb 2017
Nowhere

5·19·47 Posts

Quote:
 Originally Posted by a1call How can anyone figure that out without being a psychic?
Obviously, there was no need to be psychic. After all, at least one person did discover the trick. Now, if the answer had been, "simply guess one of the factors correctly," that might be plausibly described as having to be psychic -- or else having to cheat!

No, I didn't guess the trick of converting to base 256, and then converting the base-256 digits to ASCII. I only got as far as taking gcd's, thereby factoring the first two of the numbers. None of the other special-case factoring methods I am familiar with got anywhere in cracking the third number.

Of course, RSA moduli are routinely used to encode alphanumeric information, so the idea of converting the factors to ASCII is not quite as far-fetched as it might at first seem.

Even so, it never occurred to me. I wasn't even familiar with this particular method of converting numeric strings to text -- I had only seen the use of 2-digit blocks, and the convention that the nth letter of the alphabet corresponds to n.

However, once the answer was given, the presence of non-alphanumeric characters (and the word "characters" in the hidden message) showed that ASCII character codes were almost certainly involved. The usual text characters all have codes less than 128, and the extended ASCII character set has codes up to 255. So, assuming the characters correspond to base-b digits, the base is either 128 or 256. The shortness of text strings, and/or a little trial and error, quickly show that the base is 256. So, I learned a way to convert numeric strings to ASCII text I hadn't been familiar with.

The fact that the usual text characters all have ASCII character codes less than 128 (from 32 for a blank space to 126 for the tilde, in fact) means that the primes chosen for the puzzle are rather special. They're all over 20 digits long in base 256, four of them are intelligible text, and the fifth is the reversal of one of the other four. Since less than half the possible digits are available, the numbers of 20 digits in base 256 that render to standard text are already rarer than one in a million. And, given the specific messages encoded into the factors, I'd say that constructing them in the first place was something of a puzzle in itself.

Last fiddled with by Dr Sardonicus on 2017-05-05 at 13:48

 2017-05-05, 16:50 #32 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2·17·59 Posts I can only take some comfort in knowing that the name Armin is a Persian name. Kudos to my countryman, and anyone else who could figure this out before our after the fact. Last fiddled with by a1call on 2017-05-05 at 16:54

 Similar Threads Thread Thread Starter Forum Replies Last Post Xyzzy Puzzles 3 2018-05-05 00:20 Xyzzy Puzzles 10 2016-05-05 05:42 Batalov Puzzles 23 2015-05-05 08:43 WraithX Lounge 22 2010-04-02 04:34 HiddenWarrior Lounge 7 2004-04-08 13:27

All times are UTC. The time now is 03:31.

Sat Apr 17 03:31:48 UTC 2021 up 8 days, 22:12, 0 users, load averages: 2.10, 2.14, 2.11