No, "(a, 26) = 1" is just another way of specifying that a and 26 are relatively prime. The reason that φ(26) is 12 is that there are 12 such values of a in range.
-- Shmuel (Seymour J.) Metz http://mason.gmu.edu/~smetz3 ________________________________________ From: IBM Mainframe Discussion List [IBM-MAIN@LISTSERV.UA.EDU] on behalf of Bob Bridges [robhbrid...@gmail.com] Sent: Tuesday, August 23, 2022 6:45 PM To: IBM-MAIN@LISTSERV.UA.EDU Subject: Re: Is there a mathematician in the house? 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
