A discrepancy in literatures on permutation polynomials
in [Cryptography]
|
From: wizzi fig on 19 Jan 2010 13:21 On Jan 19, 7:57 am, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > BTW, as I indicated previously, it is my humble, maybe very incorrect, > impression that the materials you provided hithertofore are all > rather 'heuristic' in nature and one could hardly somehow attempt > to derive from them an efficient (not brute-force) procedure/algorithm > to automatically (with a computer program) obtain an H(x) desired. But I > can err, certainly. Yes, you have erred. Everything necessary is computable, given invertible P(x) mod M (with M prime) - compute the cycles of P(x) - find the GCD g of the cycle lengths - determine P'(x) = inverse of P by composing P(x) with itself g-1 times, reducing exponents using the rule x^M=x and reducing coefficients modulo M - determine H(x) = P(P'(x)+1), using the same reduction rules. > what is 'a' in the phrase 'for any a'? Shouldn't that be > u and u can be any integer? I used 'a' instead of 'alpha' used on the wiki page. If it's true for any a, it's true for the value -u/5 that I used a sentence or two earlier. If we were dealing with real numbers, a could be any real. Since we're working with numbers modulo M, a could be any integer (-u/ 5 IS an integer). Bob H
From: Mok-Kong Shen on 19 Jan 2010 17:39 wizzi fig wrote: > Mok-Kong Shen wrote: >> BTW, as I indicated previously, it is my humble, maybe very incorrect, >> impression that the materials you provided hithertofore are all >> rather 'heuristic' in nature and one could hardly somehow attempt >> to derive from them an efficient (not brute-force) procedure/algorithm >> to automatically (with a computer program) obtain an H(x) desired. But I >> can err, certainly. > > Yes, you have erred. Everything necessary is computable, given > invertible P(x) mod M (with M prime) > - compute the cycles of P(x) > - find the GCD g of the cycle lengths > - determine P'(x) = inverse of P by composing P(x) with itself g-1 > times, reducing exponents using the rule x^M=x and reducing > coefficients modulo M > - determine H(x) = P(P'(x)+1), using the same reduction rules. > >> what is 'a' in the phrase 'for any a'? Shouldn't that be >> u and u can be any integer? > > I used 'a' instead of 'alpha' used on the wiki page. If it's true for > any a, it's true for the value -u/5 that I used a sentence or two > earlier. If we were dealing with real numbers, a could be any real. > Since we're working with numbers modulo M, a could be any integer (-u/ > 5 IS an integer). Sorry, I am confused. If I don't err, you have not mentioned a wiki page before. Which wiki page is it? M. K. Shen
From: me13013 on 19 Jan 2010 21:23 On Jan 19, 5:39 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > Sorry, I am confused. If I don't err, you have not mentioned a wiki page > before. Which wiki page is it? Haha. You even quoted some text from the paragraph where I mentioned the wiki page. Now you don't think I mentioned a wiki page. I've been wondering if you've just been pulling my leg. Now, if I don't err, I am sure. Bob H
From: Mok-Kong Shen on 20 Jan 2010 11:24 me13013 wrote: > Mok-Kong Shen wrote: >> Sorry, I am confused. If I don't err, you have not mentioned a wiki page >> before. Which wiki page is it? > > Haha. You even quoted some text from the paragraph where I mentioned > the wiki page. Now you don't think I mentioned a wiki page. I've > been wondering if you've just been pulling my leg. Now, if I don't > err, I am sure. Apology. I posted at a time of very weak concentration yesterday. As far as I can see, the algorithm you detailed in a previous post could also function with composite M. For there exists a certain t such that P^t is identity and hence the inverse of P is always computable. M. K. Shen
From: Greg Rose on 20 Jan 2010 12:20
In reply to Bob: In article <hj7an5$pj6$02$1(a)news.t-online.com>, Mok-Kong Shen <mok-kong.shen(a)t-online.de> wrote: >me13013 wrote: >> Mok-Kong Shen wrote: >>> Sorry, I am confused. If I don't err, you have not mentioned a wiki page >>> before. Which wiki page is it? >> >> Haha. You even quoted some text from the paragraph where I mentioned >> the wiki page. Now you don't think I mentioned a wiki page. I've >> been wondering if you've just been pulling my leg. Now, if I don't >> err, I am sure. > >Apology. I posted at a time of very weak concentration yesterday. > >As far as I can see, the algorithm you detailed in a previous post >could also function with composite M. For there exists a certain t >such that P^t is identity and hence the inverse of P is always >computable. Yes, M-K was pulling, and continues to pull, our collective legs. That's what he does. Greg. -- Greg Rose 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C |