Ancient Cryptography

March 28, 2024, 08:31:52 AM
Welcome, Guest. Please login or register.


Ancient Cryptography » Ancient Texts » Prime Numbers » Prime Numbers and Cryptography

Author Topic: Prime Numbers and Cryptography  (Read 12837 times)

0 Members and 1 Guest are viewing this topic.

Aaron

  • Administrator
  • Sr. Member
  • Posts: 326
  • Gender: Male
Prime Numbers and Cryptography
« on: November 27, 2007, 12:36:53 PM »
As I'm sure most of you are aware, prime numbers are the key to enciphering and deciphering data sent over the internet on a day-to-day basis. However, they are also the oldest puzzle of all. What patterns have you seen in the primes, and what is the most efficient factorization method you have found? Feel free to create new topics on specific algorithms.

For further reading, I highly suggest Marcus du Sautoy's "The Music Of The Primes". It covers the more recent history of mathematics and how the search for the pattern in the primes has furthered math by leaps and bounds.

ACE Tech

  • Experimental Mathematician
  • Newbie
  • Posts: 32
  • Gender: Male
    • My Resume'
Re: Prime Numbers and Cryptography
« Reply #1 on: March 14, 2009, 02:21:18 AM »
I still don't see any discernable pattern.  Prime numbers seem to be the leftovers after all other patterns are removed.

Prime numbers increase code security when using a shifted base cipher.  If you used hexadecimal, you could also spot intelligent patterns in base 4 & base 2, for example.

I wrote a prime factoring algorithm for a high school BASIC programming project (updated & not checked for syntax):

Input X
Let PRIME_Ct =1
Do
     Let jOLD = X: ' jOLD is the last integer tested by the algorithm.

     For jTEST = 2 to INT(SQR(X)): ' The smallest prime factors are always <= Sqr(X).
          If X mod jTEST = 0
          Then
               Print jTEST : ' This is a prime factor.
               Let PRIME_Ct = PRIME_Ct +1: ' Increase the count of factors found.
               Let X = X / jTEST: ' Quotient becomes new X to be tested in the next pass of the loop.
               End For: ' Don't test this number any further, a factor has been found.
          End If
     Next jTEST:  ' Continue test for possible factors
Loop Until X = jOLD: ' No new factors have been found

If PRIME_Ct = 1 then print "This is a prime number."
Else
     Print X: ' The last factor found.
     Print "This number has these "; PRIME_Ct; " prime factors."
End If

End

Bigger primes will take longer, but the Sqr function shortens their time considerably.  Prime factors will print out smallest to largest.
« Last Edit: March 14, 2009, 05:14:12 AM by ACE Tech »
ClS0QR

Aaron

  • Administrator
  • Sr. Member
  • Posts: 326
  • Gender: Male
Re: Prime Numbers and Cryptography
« Reply #2 on: March 14, 2009, 07:35:32 AM »
Yeah, that's one of the simple programs I write when learning a new programming language. Also, there have been interesting patterns found on the complex plane, but nothing conclusive yet.
« Last Edit: March 14, 2009, 07:36:28 AM by Aaron »

ACE Tech

  • Experimental Mathematician
  • Newbie
  • Posts: 32
  • Gender: Male
    • My Resume'
Re: Prime Numbers and Cryptography
« Reply #3 on: March 14, 2009, 03:12:15 PM »
By complex plane, do you mean complex numbers?  I've only had limited involvement with those.
ClS0QR

Aaron

  • Administrator
  • Sr. Member
  • Posts: 326
  • Gender: Male
Re: Prime Numbers and Cryptography
« Reply #4 on: March 14, 2009, 03:48:10 PM »
Yeah. If you read The Music Of The Primes, the author goes into detail about patterns they were finding, mainly dealing with the probability that a number is prime in a certain range of numbers. Most of the complex math I've done deals with generating fractals, though.

ACE Tech

  • Experimental Mathematician
  • Newbie
  • Posts: 32
  • Gender: Male
    • My Resume'
Re: Prime Numbers and Cryptography
« Reply #5 on: March 15, 2009, 05:35:31 AM »
Hence the logo...
ClS0QR

Aaron

  • Administrator
  • Sr. Member
  • Posts: 326
  • Gender: Male
Re: Prime Numbers and Cryptography
« Reply #6 on: March 15, 2009, 09:33:31 AM »
Heh, yeah, I suppose you could call my avatar a type of fractal. I drew it back in high school after seeing another student make a huge doodle that uses the angular S symbol as the base element, repeated all over the place in different sizes.

milogardner

  • Newbie
  • Posts: 15
  • The Dead Sea Scrolls foretold this...
Re: Prime Numbers and Cryptography
« Reply #7 on: October 27, 2011, 05:58:01 PM »
Dear Forum members.

Reading last Tuesday's NYT's Science article, I found this interesting discussion:


"As I'm sure most of you are aware, prime numbers are the key to enciphering and deciphering data sent over the internet on a day-to-day basis. However, they are also the oldest puzzle of all. What patterns have you seen in the primes, and what is the most efficient factorization method you have found? Feel free to create new topics on specific algorithms."

For further reading, I highly suggest Pam Belluck's New York Times Science article of 12/06/10.  For 2,800 years Egyptians, Greeks, Coptics and Arabs did not rely upon an algorithm to encode rational numbers to concise unit fraction series.  Ahmes in 1650 BCE encoded 30/53 by writing

2/53(30/30) + 28/53(2/2) = 60/1590 + 56/106 = (53 + 5 + 2)/1590 + (53  + 2 + 1)/106 =

1/2 + 1/30 + 1/53 + 1/106 + 1/318 + 1/795

one of three rules used that generally encoded rational number n/p to concise unit fraction series.

More later, if anyone wishes.

Best Regards,

Milo Gardner

milogardner

  • Newbie
  • Posts: 15
  • The Dead Sea Scrolls foretold this...
Re: Prime Numbers and Cryptography
« Reply #8 on: October 27, 2011, 06:01:32 PM »
Pam Belluck's 12/6/10 NYT's Science article follows

http://www.nytimes.com/2010/12/07/science/07first.html?_r=1&amp;ref=science


Aaron

  • Administrator
  • Sr. Member
  • Posts: 326
  • Gender: Male
Re: Prime Numbers and Cryptography
« Reply #9 on: October 27, 2011, 07:22:35 PM »
Welcome, Milo! I've heard about their funky ways of dealing with fractions. Either my teachers mentioned it way back in high school or I saw it on a documentary about numbers. How would you suggest applying that to the primes?

Aaron

  • Administrator
  • Sr. Member
  • Posts: 326
  • Gender: Male
Re: Prime Numbers and Cryptography
« Reply #10 on: October 27, 2011, 07:29:22 PM »
Also, what do you mean by last Tuesday's article? Which article would that be? I know 12/6/10 is definitely farther back than last Tuesday. Your post is very confusingly structured.
« Last Edit: October 27, 2011, 07:30:56 PM by Aaron »

milogardner

  • Newbie
  • Posts: 15
  • The Dead Sea Scrolls foretold this...
Re: Prime Numbers and Cryptography
« Reply #11 on: October 28, 2011, 08:17:46 AM »
Sorry for not mentioning:

http://www.nytimes.com/2011/10/25/science/25code.html?_r=1&ref=science

The NYT's article reported the solution to a 17th century code by modern code breaking methods. Your web page is mentioned in the article, hence I looked you guys up.

I was trained in the US Army in 1957 and was assigned to Germany and Lebanon.  Discharged in 1959 I did not pick up my cryptanalytical specialist tool kit until 1990.  By chance I was asked to assist in publishing Noel Braymer's parametric-t solution to the 1650 BCE Rhind Mathematical Papyrus 2/n table problem. Noel had worked on the problem for 15 years, after seeing it in a computer puzzle magazine.  My job was to find the ancient encoding method based in prime numbers, and, as it turned out, much more.

Thank you again for the warm welcome. May our discussions be mutually beneficial.

Best Regards,

Milo Gardner
 


milogardner

  • Newbie
  • Posts: 15
  • The Dead Sea Scrolls foretold this...
Re: Prime Numbers and Cryptography
« Reply #12 on: October 28, 2011, 08:24:26 AM »
 Noel Braymers 15 years of work took another 20 years to solve to my satisfaction, summarized by:

http://planetmath.org/encyclopedia/RMP36AndThe2nTable.html

Ancient scribal number theory included many twists and turns.

Best Regards,

Milo Gardner

milogardner

  • Newbie
  • Posts: 15
  • The Dead Sea Scrolls foretold this...
Re: Prime Numbers and Cryptography
« Reply #13 on: October 28, 2011, 10:14:19 AM »
Please excuse the dumping of 20 years of research onto this discussion group.  The first formal paper that I published is mentioned in a Wikipedia article ... the Egyptian Mathematical Leather Roll ... 

http://en.wikipedia.org/wiki/Egyptian_Mathematical_Leather_Roll

The text listed 26 unit fraction series that were encoded by a student scribe that looked very different than Ahmes'  1650 BCE 2/n table reported the subject. The paper noted modern number theory patterns within a splitting method that named a parameter  A ... any composite number ... that partitioned 1/p and 1/pq.

In 2006 a second paper was published on the hekat, a volume unit used in wage payments, and storage of grain inventories. All of my paper s are available for download on Academia.edu

In 2011 a third paper began the process publishing. The paper shows the hekat was measured in beer, bread and other recipes by an inverse proportion .. a pesu ..  as an appendix that updated EMLR and RMP 2/n table scribal methods within the same ancient scribal encoding philosopy/practical methods.

Thanks again for your discussion group. Prime numbers were  written as  remainders in ways that I'll detail outside of formal algorithms.  Ahmes and Middle Kingdom scribes dropped the Old Kingdom cursive algorithm that rounded off one (1) to 1/2 + 1/4 + 1/8 + 1/16 + 1/32 + 1/64 by throwing away a 1/64 unit ... by always adding back the missing 1/64 unit in algorithmic methods.

Milo

Aaron

  • Administrator
  • Sr. Member
  • Posts: 326
  • Gender: Male
Re: Prime Numbers and Cryptography
« Reply #14 on: October 29, 2011, 12:35:14 AM »
Cool stuff! I certainly don't mind, discuss away. ;-) While I don't see this forum mentioned in the article, we have indeed discussed most of the ciphers listed in that article.

Very interesting that they used prime numbers for encoding that far back... it seems humanity has been intrigued by the primes for millenia!

milogardner

  • Newbie
  • Posts: 15
  • The Dead Sea Scrolls foretold this...
Re: Prime Numbers and Cryptography
« Reply #15 on: October 29, 2011, 08:34:57 AM »
Aaron,

Thank you for the cool comment.  Forms of the fundamental theorem of arithmetic have been with humanity  for a long time.  Counting numbers were seen every early as uniquely composed of prime numbers.

In the Ancient Egyptian base 10 era,  an infinite series algorithm limited the use of prime numbers.  Cursive rounded of binary numbers threw away 1/64 of many classes of units .  Nearby Babylonians used a related base 60  cursive round off  methodology for all if its history.

By 2050 BCE Egyptians learned to find prime numbers in remainders  that solved a  hekat volume unit scaled to (64/64).  Around 1900 BCE the Akhmim Wooden Tablet recorded the (64/64) scaled unit divided by 3, 7, 10, 11 and 13. For example: divisor 3 was written as 1/s such that

(64/64)/3 = 21/64 + 1/192

Primes enter the discussion by scaling the remainder 1/192 by (5/5) and 5/960

with a 1/320 of a hekat unit named ro

with the complete answer found by considering

( 16 + 4 + 1)/64 +  (5/3)ro

(1/4 + 1/16 + 1/64)hekat + (1+ 2/3)ro

The next three problems divisor 7, 10 and 11 will be skipped.

Let me conclude with the divisor 13 case:

(64/64)/13 = 4/64 + (60/13)ro

(1/16) hekat + (4 + 8/13) ro

with 2/n table and RMP scaling of rational rules created:

8/13(2/2) =  16/26 = (13 + 2 + 1)/26 = 1/2 + 1/13 + 1/26

with the final answer recorded as

(1/16)hekat + (4+ 1/2 + 1/13 + 1/26)ro

The AWT scribe proved the accuracy of his five answers, by multiplying by the initial divisor, a fun exercise for anyone new to Egyptian fraction math.

Best Regards,

Milo Gardner

 




milogardner

  • Newbie
  • Posts: 15
  • The Dead Sea Scrolls foretold this...
Re: Prime Numbers and Cryptography
« Reply #16 on: October 29, 2011, 10:07:44 AM »
Aaron,

Wikipedia includes an incomplete Akhmim Wooden Tablet entry:

http://en.wikipedia.org/wiki/Akhmim_wooden_tablets

The scribal calculation

(64/64)/3 = [21/64 + 1/192(5/5)] = (16 + 4 + 1)/64 hekat + (5/3)ro ro

reported the correct answer

(1/4 + 1/16 + 1/64)hekat + (1 + 2/3)ro

Scribal errors were oddly stressed in the Wikipedia article. Historically the scribe was required to prove the accuracy of  this  class of calculation by multiplying by the initial divisor 3.

Wikipedia should be corrected to include the historical  proof step

[21/64 + 5/3(1/320)] x 3 = (63/64 + 1/64) = 64/64

as Hana Vymazalova published in 2002, properly naming (64/64)  a hekat unity.

Thanks again for the discussion. Since I am mentioned on Wikipedia, it would be improper for me to submit the update to include the proof.

Milo Gardner

Aaron

  • Administrator
  • Sr. Member
  • Posts: 326
  • Gender: Male
Re: Prime Numbers and Cryptography
« Reply #17 on: November 01, 2011, 11:13:50 PM »
Ah, so not only was it intended to encrypt on some level, it was also intended to guard against errors in writing! That sounds a lot like the challenges faced by data transmission even today, which I learned about in my computer science classes on networking.

milogardner

  • Newbie
  • Posts: 15
  • The Dead Sea Scrolls foretold this...
Re: Prime Numbers and Cryptography
« Reply #18 on: November 02, 2011, 12:30:57 PM »
Aaron,

Thank you for the modern double checking metaphor  needed by computers. The issue of double check offers a timeless quality. The longer term issue is discussed by one modern example, by my 10 year old grandson Adam, and Ahmes' 1650 BCE  mutiplicationt of one hekat recorded as 320 ro times 7/22.

Concerning my grandson,  many math problems require double checking by a different method than first calculated. Adam loves to work problems in his head, infrequently writing down his work. As he gets older hopefully he'll enjoy showing his work,  and double checking by a different method, a well known rule used by students of mathematics at any age.

Concerning Ahmes,  he did not consider RMP 38's writing of

320 ro times 7/22 = 2240/22 =  (101 +  9/11)ro 

restated 9/11 to a unit fraction series as a code.  Unit  fraction math was the arithmetic of his era.

Today reading Ajmes' work, the details  act like a code,  double checked by considering:

(101 + 9/11)ro  times 22/7 =  320 ro = 1 hekat  (as we would say ... Q.E.D.)

I could go on and discuss the issue of round counter volumes recorded in hekats that set pi = 256/81
that overestimated pi and hekat units.  Of course 22/7 would have been an improved estimate for pi; however, historians have not directly decoded this aspect of ancient Egyptian weights and measure mathematics.

Milo

escher7

  • Newbie
  • Posts: 16
  • The Dead Sea Scrolls foretold this...
Re: Prime Numbers and Cryptography
« Reply #19 on: November 25, 2011, 05:18:06 AM »
You guys are way over my head. My understanding of the main prime number issue is the difficulty in factoring the product of two large primes, (quadratic sieves, Eratosthenes etc.). It is easy to multiply them, but knowing the product it is almost impossible to go the other way for very large numbers, hence the security of current crypto standards. The NSA is always paranoid that someone will come up with shortcut method, giving them access to classified communications. They probably already have. I haven't read anything in this area for years, but I recall when some mathematician in India had substantially improved upon the quadratic sieve method, causing some concern.

In my drinking days, and I was a pro for many years, I had a tendency to do dumb things late at night, like phone up or email  intelligence services and pull their leg. (Not a terribly bright thing to do, but hey, I'm a Canadian eh.) Anyway, one night when I was on a second forty of rum, accented sporadically by shots of Crown Royal, a guy showed up in the grungy local bar that I frequented because I could walk home. He looked out of place and made a point of standing close to me at the bar. We started talking and it turned out he had a heavy background in engineering. Somehow the conversation gravitated to mathematics and he took a very pointed interest in my conversation about factoring primes, particularly my knowledge of recent developments like the one in India. I had been reading a lot and sounded knowledgeable even if I was really not. You have to understand, this place was several steps down from a biker bar and most patrons had trouble with English, never mind anything academic. He kept leading me back to the topic, trying to see how much I really knew. Fortunately, I was getting pretty blurry and I kept wandering off point until he gave up and promptly walked away.

To this day I remain convinced that my shenanigans with emailing NSA had prompted someone to come out and find out if I was a risk. They seemed to have realized I was just a drunk, and I never saw the guy again. I quit pestering the three letter boys after that.

Glad to see sites like this keeping the conversation alive.

 


anything