1 + 2^a + 2^b = k*p
in [Math]
|
From: M.A.Fajjal on 17 May 2010 23:45 1 + 2^a + 2^b = k*p p is a given prime a,b in {0,1,2,....(p-3)/2} k is integer a,b,k can be determined by sequential search Is there any way to get direct solution?
From: James Waldby on 18 May 2010 16:01 On Tue, 18 May 2010 03:45:14 -0400, M.A.Fajjal wrote: > 1 + 2^a + 2^b = k*p > p is a given prime > a,b in {0,1,2,....(p-3)/2} > k is integer > > a,b,k can be determined by sequential search > Is there any way to get direct solution? It seems to me that fast solution methods for this need fast solutions of the somewhat-challenging discrete logarithm problem. See eg <http://en.wikipedia.org/wiki/Discrete_logarithm_problem>. Below is an O(p) method, based on 2^b mod p == p - 1 - 2^a. [Ie, let s(a,b) = 1 + 2^a + 2^b. s(a,b) = k*p for some k --> s(a,b) mod p == 0 --> 2^a + 2^b mod p == p-1 --> 2^b mod p == p - 1 - 2^a.] Method: 1. Initialize array f[] with p/2 entries to zeroes (or if doing many values of p, also use an array of generation numbers to avoid O(p) initialization costs). 2. For a from 1 to p/2-2, do steps 2.1-2.4 .1 Compute r = (2^a mod p) in O(1) time. .2 Set f[r] = a and b = f[p-1-r]. .3 If b>0, report solution (a,b) .4 If b>0 and only seeking 1 solution, exit For example, with p=23, this would report solutions (2,6) [s=69=3*23], (4,9) [s=529=23*23], and (5,7) [s=161=7*23], and with p=89, no solutions. (Note, the algorithm could terminate the inner loop early when a>1 and r=1; eg, 2^11 = 2048 == 1 mod 89.) -- jiw
From: Chip Eastham on 19 May 2010 00:09 On May 18, 3:45 am, "M.A.Fajjal" <h2...(a)yahoo.com> wrote: > 1 + 2^a + 2^b = k*p > > p is a given prime > > a,b in {0,1,2,....(p-3)/2} > > k is integer > > a,b,k can be determined by sequential search > > Is there any way to get direct solution? Since there is no solution unless p >= 3, and 3 = 1+1+1, let's restrict consideration to odd primes p > 3. I'm not sure what motivates this question. Solutions are not always unique, e.g. 17 = 1 + 2^3 + 2^3 but 17 also divides 34 = 1 + 1 + 2^5. In the case that 2 is a primitive root mod p, we can give a "direct" solution in that: 2^((p-1)/2) = -1 mod p, so: p | 1 + 2^a + 2^b when a,b = (p-3)/2. Indeed the above requires only that 2^((p-1)/2) = -1 mod p, not primitivity of 2, so for example the construction works for p = 17 despite 2 having only order 8 in Z/17Z. It is easy to verify that the smallest exponent for 2^m = -1 mod p, if it exists, is less than or equal to (p-1)/2. So the cases that remain are primes p like 7, 23, and 47 in which no such exponent exists. For these we seek solutions with a < b: 1 + 2 + 4 = 7 1 + 2^2 + 2^6 = 5*23 1 + 2^2 + 2^9 = 11*47 However in some cases there is no solution. For p = 31 the powers of 2 mod p are 1,2,4,8,16, and it is not possible to find a,b s.t. 1 + 2^a + 2^b is divisible by 31. All of this suggests a "direct" solution is unlikely except for cases where a=b and 2^(a+1) = -1 mod p. regards, chip
|
Pages: 1 Prev: Cheap drugs online FDA-approved Next: Computation of definite integral of Sin(x)/x and more |