https://en.wikipedia.org/wiki/Euler%27s_totient_function
Sent from my iPad > On 23 Aug 2022, at 23:45, Bob Bridges <robhbrid...@gmail.com> wrote: > > Comment from another knowledgeable cove: > > "In number theory, Euler's totient function counts the positive integers up > to a given integer n that are relatively prime to n. It is written using the > Greek letter phi as φ(n) or ϕ(n), and may also be called Euler's phi > function. In other words, it is the number of integers k in the range 1 ≤ k ≤ > n for which the greatest common divisor gcd(n, k) is equal to 1. The integers > k of this form are sometimes referred to as totatives of n." > > First of all, yeah, "relatively prime", not "mutually prime" as I wrote > below. It didn't seem quite right even at the time, though I suppose it was > clear enough. > > So "(a, 26) = 1", I guess, is just another way of specifying why φ(26) is 12. > I can take up the chapter again, now. > > --- > Bob Bridges, robhbrid...@gmail.com, cell 336 382-7313 > > /* Canada could have had the culture of France, the entrepreneurial spirit of > the US and the British tradition of tolerance. Instead it got the culture of > the US, the entrepreneurial spirit of Britain and the French tradition of > tolerance. */ > > -----Original Message----- > From: robhbrid...@gmail.com <robhbrid...@gmail.com> > Sent: Tuesday, August 23, 2022 17:12 > > Ah, so "(a, 26) = 1" simply states what I had already figured out, that there > must be no common factors between them. (Not counting 1 itself, of course.) > I think I read once that another way of saying that is "<a> and 26 are > mutually prime". Thanks, Horacio. > > I'm thinking that in one sense there are actually an infinite number of > values that will work for <a>, but once you get to 26 and past they're simply > repeating previous values. For instance, if you use 3 (and I'll pretend b=0 > just for simplicity here) then the ciphertext numbers are 3, 6, 9, 12, 15, > 18, 21, 24, 1, 4, 7, 10, 13, 16, 19, 22, 25, 2, 5, 8, 11, 14, 17, 20, 23, 26. > I could also use a=29, 55, 81 and so on, but the ciphertext sequence is > identical so there's no point. > > -----Original Message----- > From: IBM Mainframe Discussion List <IBM-MAIN@LISTSERV.UA.EDU> On Behalf Of > Horacio Luis Villa > Sent: Tuesday, August 23, 2022 17:01 > > (m,n) is the great common divisor between m and n. > Can't tell what phi(26)=12 is, but I would say is something like "there are > 12 coprimes among the 26 first natural numbers". > > ________________________________ > De: IBM Mainframe Discussion List <IBM-MAIN@LISTSERV.UA.EDU> en nombre de Bob > Bridges <robhbrid...@gmail.com> > Enviado: martes, 23 de agosto de 2022 17:50 > > I got to talking with a church friend about encryption, and at lunch > yesterday he lent me a book on number theory that has a chapter on asymmetric > encryption. Cryptography has long been a hobby of mine, but it's only > recently that I came to understand a little of how asymmetric encryption can > work. > > The chapter I'm perusing will get into asymmetric encryption eventually, but > it's starting with simple rotational ciphers. Expanding on the simple > rotation, it then talks about something it calls "affine transformations", > which introduce an additional term into the formula used to encrypt or > decrypt the text: > > C ≡ <a>P+<b> (mod 26) 0 ≤ C ≤ 25 > > ...where, it specifies, "(a, 26) = 1". Here's where I pause: What operation > is indicated by "(m, n)"? > > It goes on to say that for 26 letters in the cipher, "there are ф(26) = 12 > choices for <a>". I can see that <a> and 26 must have no factors in common > for this to work, and without actually working out how many choices there are > I can easily believe the answer is 12, but what function is implied by phi? > > ---------------------------------------------------------------------- > For IBM-MAIN subscribe / signoff / archive access instructions, > send email to lists...@listserv.ua.edu with the message: INFO IBM-MAIN ---------------------------------------------------------------------- For IBM-MAIN subscribe / signoff / archive access instructions, send email to lists...@listserv.ua.edu with the message: INFO IBM-MAIN
