mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2017-05-04, 03:03   #23
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2·17·59 Posts
Default

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
a1call is offline   Reply With Quote
Old 2017-05-04, 05:09   #24
Harrywill
 
"Harry Willam"
May 2017
USA

22·5 Posts
Default 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?
Harrywill is offline   Reply With Quote
Old 2017-05-04, 15:26   #25
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

5×19×47 Posts
Default

Quote:
Originally Posted by a1call View Post
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 )
Dr Sardonicus is offline   Reply With Quote
Old 2017-05-04, 17:25   #26
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

7D616 Posts
Default

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?
a1call is offline   Reply With Quote
Old 2017-05-04, 20:55   #27
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

5×19×47 Posts
Default

Quote:
Originally Posted by a1call View Post
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
Dr Sardonicus is offline   Reply With Quote
Old 2017-05-04, 22:32   #28
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2·17·59 Posts
Default

Very impressive, thank you so much.
a1call is offline   Reply With Quote
Old 2017-05-05, 04:39   #29
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

33·347 Posts
Default

Of course I didn't figure it out.

But now after the war, there are a lot of heroes, so let's be one of them: I disagree that one needs to be a psycho to be able to do so. The solution is extremely simple, and the puzzle IS ingenious.

Our problem is that we are spoiled by the tools we use every day, they are done by other people, and we use them without understanding their internal kitchen. Like when you drive a car for 10 years, and you don't know anymore what's happening when you step on the gas pedal, except that the car goes faster.

The common sense dictates that there is something tricky here, because otherwise the problem is not addressed to the large public, but to an extremely small audience (guys like us who like to factor numbers). They addressed the problem to a much larger audience, and there should be some kind of "IQ test" here (which we failed - the royal we).

There must be more to it than "use yafu to factor these 3 (easy) numbers". That is why in fact I didn't report "my" solution. Too easy, not fun. See my posts above.

In fact, for some guy having no idea of msieve, yafu, whatever, the first impulse would be to make the GCD's to look for any possible common factors. Yes! They didn't give you a problem that would require you to search endless databases with factors, neither to learn GNFS overnight (I still can't grasp these advanced factoring stuff completely, after years, and I have the "pride" to be a math-educated guy). So, you have to make some simple GCD, and in doing so, you will need to create a small piece of code to handle the size of the numbers, eventually print this numbers in hex (or save them in a file in binary, whatever, all these are simple tasks and they will occur, if you try to think for yourself -- solve the problem with your own mind, not use black-box tools, and then, by "intelligence", "chance", some luck, whatever, you will immediately spot the ascii characters in the file, with any text editor, one can then clearly see the message in the text. It may require a bit of "out of the box" thinking, but you do not need to be some genius or psycho to do that...

Click image for larger version

Name:	encry.PNG
Views:	67
Size:	30.1 KB
ID:	16040

(sorry, the writebin was not the right command, as it writes some crap in the file related to the structure of the variable, and some magic number to recognize the file when read back, see the user manual)

Opening the file with ANY text editor (not aware of the binary stuff) just shows you the text.

Click image for larger version

Name:	encry2.PNG
Views:	72
Size:	15.5 KB
ID:	16041

Yes, this is exactly the same file, this time shown in the lister with the binary turned off, and shown in the notepad too, for clarity. In fact, you can just type your text in notepad, save the file, then look to it with a hex editor and see what "number" does it make - here is the "ingenious" part of the puzzle, the author did some research to have this number prime, and its reverse be prime too, and additionally to offer you a hint...

Brilliant!

But that is another discussion.

Our problem (collective we) was that we used tools to do the job for us, and even didn't look to the result.

Before people here on this thread told me to look deeper to the factors, I even didn't remark that the factors are the same! Shame! Totally! I completely relied on the black-box tools.

Well... All in all, very nice trick!
(We didn't want to say "nice problem" because then we will lose face, contradicting what we said few posts above, haha ).

Last fiddled with by LaurV on 2017-05-05 at 05:10
LaurV is offline   Reply With Quote
Old 2017-05-05, 08:00   #30
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2·36 Posts
Default

For a real world example of the puzzle see the 7-th page of https://smartfacts.cr.yp.to/smartfacts-20130916.pdf (batch gcd).
R. Gerbicz is offline   Reply With Quote
Old 2017-05-05, 13:45   #31
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

5·19·47 Posts
Default

Quote:
Originally Posted by a1call View Post
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
Dr Sardonicus is offline   Reply With Quote
Old 2017-05-05, 16:50   #32
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2·17·59 Posts
Default

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
a1call is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
April 2018 Xyzzy Puzzles 3 2018-05-05 00:20
April 2016 Xyzzy Puzzles 10 2016-05-05 05:42
April 2015 Batalov Puzzles 23 2015-05-05 08:43
April Fooling... WraithX Lounge 22 2010-04-02 04:34
April 1, 2004 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.