Help! I need help!

Leannemarie1993

New member
Joined
Jul 6, 2020
Messages
5
I am really hoping someone can help me! I am trying to find 2 factors of the following 200 digit number... 54619522885803207472214374630191243250590849559339873137094091593337339221786396696811095226208192838718744501839769111014269112362134026658675162985744645309833621088720000513632839305234305983970941

Can anyone point me in the right direction on how to get an answer!

TYIA
 
No problem. Just sequentially try dividing it by each prime up to its square root. Method guaranteed to get an answer. 8-)
Thanks for your response. We have 2 issues, no calculator big enough and we don't have a list of all of the prime numbers up to 100 digits long
 
You need to know the divisibility rules. Try the rule for 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,... . I hope that you see that no even number goes into your number
 
For those unfamiliar with the topic of factoring large integers which are the products of two large primes, this site might be informative:'

Even 200 digit problems as above are non-trivial.
 
Thanks for your response. We have 2 issues, no calculator big enough and we don't have a list of all of the prime numbers up to 100 digits long
Yes. I know that. I was trying to figure out why you posted the question in the first place. Are (were) you unfamiliar with the RSA challenge problems I linked to in post #5? Look at the comments after RSA 200.
 
Thanks for your response. We have 2 issues, no calculator big enough and we don't have a list of all of the prime numbers up to 100 digits long
There is always a chance that you can find factors long before you get into 100 digits numbers.

Have you tried the divisibility rule for 3, 9 and 11. They both involve simple addition and subtraction of the numbers.

A number is divisible by 3 or 9 if the sum of the digits is divisible by 3 or 9. When you add the numbers just ignore digits that are multiples of 3 and mod out 3's as you add.

For 11, compute 1st digit - 2nd digit + 3rd digit - ... - 200th digit. See if that number is divisible by 11.
 
Given that the OP wants "2 factors" I assume she is telling us that this 200 digit number is the product of 2 primes. If it's a typical RSA product of primes type problem it would be intentionally created as the product of two approximately 100 digit primes. Perhaps it is someone's public RSA key she is hoping to crack. Simple factoring techniques that you might try by hand are infeasible. I wish the OP would explain where she got this number and why she wants to factor it. And why she thinks anyone would try.
 
Given that the OP wants "2 factors" I assume she is telling us that this 200 digit number is the product of 2 primes. If it's a typical RSA product of primes type problem it would be intentionally created as the product of two approximately 100 digit primes. Perhaps it is someone's public RSA key she is hoping to crack. Simple factoring techniques that you might try by hand are infeasible. I wish the OP would explain where she got this number and why she wants to factor it. And why she thinks anyone would try.
Morning! I have read the article on RSA thank you. The reason I asked is because I am looking for coordinates. This number was given as part of a puzzle to finding the coordinates, once the two factors are known, I then need to use those numbers as part of an equation which will, hopefully, give me the coordinates I need. I have messaged the owner of the puzzle as it has never been found before and he was not willing to give me any clues which is why I came here for help! I have tried everything I can think of, but not getting anywhere. I have a calculator running, and it has been running for 4 days however, it is only on 9 digits for each factor. Assuming each factor will have around 100 digits, I fear retiring before the calculator finishes!
 
Context is very important here.

I take it this is something like a geocache puzzle. It may be important to show us the exact wording of the entire puzzle (e.g. the whole description), as there could be a useful clue hidden in the words somewhere.

Or, it might really be a puzzle that could take years to solve, and is meant mostly to frustrate people.
 
Context is very important here.

I take it this is something like a geocache puzzle. It may be important to show us the exact wording of the entire puzzle (e.g. the whole description), as there could be a useful clue hidden in the words somewhere.

Or, it might really be a puzzle that could take years to solve, and is meant mostly to frustrate people.
Correct! This is the wording.

The task is simply stated. Just find the two factors1 of the rather large number below. Then extract from the factors the digits indicated to find the coordinates.
The number is:
54619522885803207472214374630191243250590849559339
87313709409159333733922178639669681109522620819283
87187445018397691110142691123621340266586751629857
44645309833621088720000513632839305234305983970941
 
I asked for the entire puzzle. You've clearly omitted something, since nothing here shows "the digits indicated". Even the name of the puzzle (cache?) might be a clue.
 
I asked for the entire puzzle. You've clearly omitted something, since nothing here shows "the digits indicated". Even the name of the puzzle (cache?) might be a clue.
The digits were infact included in my last reply, unsure why you cannot see them. Please see the whole post (below). I have messaged the creator who has not given me a hint but has given me the reasoning behind such an 'evil' puzzle. Please let me know if you have any issues with viewing the post. I may be able to get a link to the page?

Many thanks

I devised and set “Possible Prime Provides Problematic Puzzle” (GC7Y78T) intending it to be a very difficult puzzle. I was, therefore, amazed when somebody solved the puzzle within 6 hours, and there was a FTF from a second solver only 12 hours after the cache was published!
Unfortunately, I had made a couple of foolish errors that allowed the cache to be located fairly easily. One method involved a short cut to finding the factors, the other way simply required some lateral thinking.
The history of failed ciphers is littered with ‘lazy’ operators and ‘clever strategies’ that, whilst supposedly making the cipher more complex, actually introduced weaknesses that could be exploited by the code-breakers.
Perhaps the most famous of these weaknesses was in a refinement to Germany’s Enigma coding machine in the Second World War. The original machine had three rotors which, each in turn, scrambled the letter fed into it, yielding millions of possibilities, and changing the combinations after each letter. An early refinement to the machine put a “reflector” at the end of the three rotors so the letter was passed back along the chain of rotors one more time, scrambling each letter a total of six times, instead of three. The code-makers believed this would make the enigma code even more secure, even unbreakable. Unfortunately, they failed to realise a simple flaw. Doing this meant that, due to the design of the machine, a letter could never be encoded back to itself. i.e. an ‘A’ could be encoded to any letter *except* ‘A’. This allowed the code-breakers to target fragments of the message with phrases that they believed were in the message. (Contrary to what was shown in a popular film, the most commonly targeted phrases were weather based, ‘wind speed’, ‘visibility’ etc, not “Heil Hitler”). This weakness is what ultimately led to the breaking of the Enigma Code.
This puzzle doesn’t, I hope, succumb to any such weaknesses and should prove *very* hard to solve.
The task is simply stated. Just find the two factors1 of the rather large number below. Then extract from the factors the digits indicated to find the coordinates.
The number is:
54619522885803207472214374630191243250590849559339
87313709409159333733922178639669681109522620819283
87187445018397691110142691123621340266586751629857
44645309833621088720000513632839305234305983970941
The coordinates are:
Northings - use the smallest factor:
N52 [32-33].[41-43]
Eastings - use the largest factor:
W000 [13-14].[20-22]

1. There is just the slightest chance, only one chance in several billion, that there are more than two factors. If you are lucky enough to prove that there are more than two factors, then please let me know and carry on using the two largest factors you found.
 
The digits were infact included in my last reply, unsure why you cannot see them. Please see the whole post (below). I have messaged the creator who has not given me a hint but has given me the reasoning behind such an 'evil' puzzle. Please let me know if you have any issues with viewing the post. I may be able to get a link to the page?

When I said you didn't show "the digits indicated", I meant the indication of which digits to use, which turns out to be this: "The coordinates are: Northings - use the smallest factor: N52 [32-33].[41-43], Eastings - use the largest factor: W000 [13-14].[20-22]". Not that we need that to solve the puzzle, but that this was clearly omitted, so I was hoping that some omitted words might include clues to make it easier. (They do the opposite.)

Also, now I can make sense of "factors1", seeing that the 1 is a footnote number.

They are claiming that this should be harder than Enigma to break, with none of the "weaknesses" I hoped to find in the text; this supports the level-5 difficulty (which I saw on locating the cache entry itself). So you'll have to study advanced ways to factor large numbers, and likely use a computer program to do it. I suggest you read up on techniques for doing this (for example, this is mentioned in the article previously referred to); I have no special knowledge of that, and certainly no intention to try doing it myself.

Have fun!
 
When I said you didn't show "the digits indicated", I meant the indication of which digits to use, which turns out to be this: "The coordinates are: Northings - use the smallest factor: N52 [32-33].[41-43], Eastings - use the largest factor: W000 [13-14].[20-22]". Not that we need that to solve the puzzle, but that this was clearly omitted, so I was hoping that some omitted words might include clues to make it easier. (They do the opposite.)

Also, now I can make sense of "factors1", seeing that the 1 is a footnote number.

They are claiming that this should be harder than Enigma to break, with none of the "weaknesses" I hoped to find in the text; this supports the level-5 difficulty (which I saw on locating the cache entry itself). So you'll have to study advanced ways to factor large numbers, and likely use a computer program to do it. I suggest you read up on techniques for doing this (for example, this is mentioned in the article previously referred to); I have no special knowledge of that, and certainly no intention to try doing it myself.

Have fun!
Dr. Peterson, apparently you have found the source of the puzzle? Please give a link. Also, @Leannemarie1993 are you studying computer science? Are you current with state of the art factoring techniques? Do you understand the magnitude of effort needed to factor that number if it is indeed the product of two 100 digit primes? Are you an expert in that field or just passing the time musing about the puzzle? I know enough about the subject to know it isn't worthwhile wasting time on this problem.
 
Top