| View previous topic :: View next topic |
| Author |
Message |
JSH
Guest
|
 Posted: Sun Jun 22, 2008 2:26 pm Post subject: JSH: Probabilistic quadratic residue solving |
 |
|
An off-shoot of my surrogate factoring research is a probabilistic
method to solve quadratic residues, as given
k^2 = q mod p
when p is an odd prime, and q is a quadratic residue modulo p, you
find k.
The technique requires introduction of a few additional variables
starting with T, where
T = 2q + np
where n is an odd natural number so you have T = 2q mod p, but T - 2q
is also forced to have p as a factor.
Next you find z, where with integer factors f_1 and f_2 where f_1*f_2
= T:
z = (f_1 + f_2)/2
and now finally you try for an answer for k, with
k = 3^{-1}(2z) mod p.
The method is probabilistic because if I've got the analysis right you
have a 50% probability of getting the right k, for each z that you
try. Checking is done by looking at k^2 mod p, to see if you get q.
Example: Let q=2, p=17 so T = 2(2) mod 17 = 4 mod 17.
Here T=21 does not work, but T = 55 = 5(11), so z = 8 and the answer
then from
3k = 2( mod 17, is k = 11 mod 17.
Is there any use for such a technique?
James Harris |
|
| Back to top |
|
 |
| |
Ads |
Advertising
Sponsor
|
|
Chip Eastham
Guest
|
| Posted: Sun Jun 22, 2008 3:11 pm Post subject: Re: JSH: Probabilistic quadratic residue solving |
|
|
On Jun 22, 10:26 am, JSH <jst...@gmail.com> wrote:
[snip]
| Quote: |
The method is probabilistic because if I've got the analysis right you
have a 50% probability of getting the right k, for each z that you
try. Checking is done by looking at k^2 mod p, to see if you get q.
Example: Let q=2, p=17 so T = 2(2) mod 17 = 4 mod 17.
Here T=21 does not work, but T = 55 = 5(11), so z = 8 and the answer
then from
3k = 2( mod 17, is k = 11 mod 17.
Is there any use for such a technique?
James Harris
|
For primes p = 8n + 1, there is a probabilistic aspect
of the best methods for finding square roots mod p.
For primes with other residues mod 8, deterministic
methods are known.
However the nondeterminism is limited to finding one
quadratic residue mod p. If only one square root mod
p is needed, then perhaps the analysis comes to the
same thing, but it is well known that half of all the
nonzero residues mod p are quadratic nonresidues, and
confirming one by Legendre symbol (efficiently found
by the generalization, the Jacobi symbol) chosen at
random clearly gives a 50% chance of success.
The Wikipedia articles on "Quadratic residue" and
"Shanks-Tonelli algorithm" would be nice starting
points if you wish know more.
regards, chip |
|
| Back to top |
|
|
| |
Ads |
Advertising
Sponsor
|
|
George Orwell
Guest
|
| Posted: Sun Jun 22, 2008 3:25 pm Post subject: Re: JSH: Probabilistic quadratic residue solving |
|
|
Our chief resident crank pondered
| Quote: |
An off-shoot of my surrogate factoring research is
a probabilistic method to solve quadratic residues,
as given
|
(snip some of his usual crap)
| Quote: |
Is there any use for such a technique?
|
To give you something to further clutter up these NGs with
unmitigated fecal analysis?
But we still luvya anyways!!!
Xs & Os
Il mittente di questo messaggio|The sender address of this
non corrisponde ad un utente |message is not related to a real
reale ma all'indirizzo fittizio|person but to a fake address of an
di un sistema anonimizzatore |anonymous system
Per maggiori informazioni |For more info
https://www.mixmaster.it |
|
| Back to top |
|
|
| |
Ads |
Advertising
Sponsor
|
|
JSH
Guest
|
| Posted: Sun Jun 22, 2008 4:04 pm Post subject: Re: JSH: Probabilistic quadratic residue solving |
|
|
On Jun 22, 8:11 am, Chip Eastham <hardm...@gmail.com> wrote:
| Quote: |
On Jun 22, 10:26 am, JSH <jst...@gmail.com> wrote:
[snip]
The method is probabilistic because if I've got the analysis right you
have a 50% probability of getting the right k, for each z that you
try. Checking is done by looking at k^2 mod p, to see if you get q.
Example: Let q=2, p=17 so T = 2(2) mod 17 = 4 mod 17.
Here T=21 does not work, but T = 55 = 5(11), so z = 8 and the answer
then from
3k = 2( mod 17, is k = 11 mod 17.
Is there any use for such a technique?
James Harris
For primes p = 8n + 1, there is a probabilistic aspect
of the best methods for finding square roots mod p.
For primes with other residues mod 8, deterministic
methods are known.
|
Well this technique would be probabilistic for p odd prime.
So it's more general then, correct?
| Quote: |
However the nondeterminism is limited to finding one
quadratic residue mod p. If only one square root mod
p is needed, then perhaps the analysis comes to the
same thing, but it is well known that half of all the
nonzero residues mod p are quadratic nonresidues, and
confirming one by Legendre symbol (efficiently found
by the generalization, the Jacobi symbol) chosen at
random clearly gives a 50% chance of success.
|
Um, yeah.
| Quote: |
The Wikipedia articles on "Quadratic residue" and
|
Already read it.
| Quote: |
"Shanks-Tonelli algorithm" would be nice starting
|
Thanks! Just went by to check it out.
| Quote: |
points if you wish know more.
|
I think it interesting to me that what I call surrogate factoring
leads to this way to solve for a quadratic residue by factoring. Note
my idea involves factoring an odd T chosen such that T = 2q mod p,
where q is the quadratic residue modulo p, and it should have a 50%
chance of success with each factorization of T, if it's right.
The math is easy but repeatedly I've thought one thing and been forced
to back down later when experiments demonstrate that I'm wrong. Still
I find myself drawn in a bit on this subject so I'm reading material
about it on the web and pondering the problem.
___JSH |
|
| Back to top |
|
|
| |
Ads |
Advertising
Sponsor
|
|
rossum
Guest
|
| Posted: Sun Jun 22, 2008 10:51 pm Post subject: Re: JSH: Probabilistic quadratic residue solving |
|
|
On Sun, 22 Jun 2008 09:04:10 -0700 (PDT), JSH <jstevh@gmail.com>
wrote:
| Quote: |
On Jun 22, 8:11 am, Chip Eastham <hardm...@gmail.com> wrote:
On Jun 22, 10:26 am, JSH <jst...@gmail.com> wrote:
[snip]
The method is probabilistic because if I've got the analysis right you
have a 50% probability of getting the right k, for each z that you
try. Checking is done by looking at k^2 mod p, to see if you get q.
Example: Let q=2, p=17 so T = 2(2) mod 17 = 4 mod 17.
Here T=21 does not work, but T = 55 = 5(11), so z = 8 and the answer
then from
3k = 2( mod 17, is k = 11 mod 17.
Is there any use for such a technique?
James Harris
For primes p = 8n + 1, there is a probabilistic aspect
of the best methods for finding square roots mod p.
For primes with other residues mod 8, deterministic
methods are known.
Well this technique would be probabilistic for p odd prime.
So it's more general then, correct?
If you want a more general probabilistic algorithm, then yes. If you |
want a deterministic algorithm then no. For myself I use the
deterministic algorithms (p mod 8 = 3, 5, 7) where possible and only
use the probabilistic algorithm (p mod 8 = 1) where I have to.
Crandall and Pomerance, algorithm 2.3.8 refers.
YMMV.
| Quote: |
However the nondeterminism is limited to finding one
quadratic residue mod p. If only one square root mod
p is needed, then perhaps the analysis comes to the
same thing, but it is well known that half of all the
nonzero residues mod p are quadratic nonresidues, and
confirming one by Legendre symbol (efficiently found
by the generalization, the Jacobi symbol) chosen at
random clearly gives a 50% chance of success.
Um, yeah.
The Wikipedia articles on "Quadratic residue" and
Already read it.
"Shanks-Tonelli algorithm" would be nice starting
Thanks! Just went by to check it out.
points if you wish know more.
I think it interesting to me that what I call surrogate factoring
leads to this way to solve for a quadratic residue by factoring. Note
my idea involves factoring an odd T chosen such that T = 2q mod p,
where q is the quadratic residue modulo p, and it should have a 50%
chance of success with each factorization of T, if it's right.
The math is easy but repeatedly I've thought one thing and been forced
to back down later when experiments demonstrate that I'm wrong.
You should consider this observation well James. |
rossum
| Quote: |
Still I find myself drawn in a bit on this subject so I'm reading
material about it on the web and pondering the problem.
___JSH
|
|
|
| Back to top |
|
|
| |
Ads |
Advertising
Sponsor
|
|
Larry Hammick
Guest
|
| Posted: Sun Jun 22, 2008 11:07 pm Post subject: Re: Probabilistic quadratic residue solving |
|
|
"JSH"
| Quote: |
An off-shoot of my surrogate factoring research is a probabilistic
method to solve quadratic residues, as given
k^2 = q mod p
when p is an odd prime, and q is a quadratic residue modulo p, you
find k.
The technique requires introduction of a few additional variables
|
LOL |
|
| Back to top |
|
|
| |
Ads |
Advertising
Sponsor
|
|
Chip Eastham
Guest
|
| Posted: Tue Jun 24, 2008 2:46 am Post subject: Re: JSH: Probabilistic quadratic residue solving |
|
|
On Jun 22, 10:26 am, JSH <jst...@gmail.com> wrote:
| Quote: |
An off-shoot of my surrogate factoring research is a probabilistic
method to solve quadratic residues, as given
k^2 = q mod p
when p is an odd prime, and q is a quadratic residue modulo p, you
find k.
The technique requires introduction of a few additional variables
starting with T, where
T = 2q + np
where n is an odd natural number so you have T = 2q mod p, but T - 2q
is also forced to have p as a factor.
Next you find z, where with integer factors f_1 and f_2 where f_1*f_2
= T:
z = (f_1 + f_2)/2
and now finally you try for an answer for k, with
k = 3^{-1}(2z) mod p.
The method is probabilistic because if I've got the analysis right you
have a 50% probability of getting the right k, for each z that you
try. Checking is done by looking at k^2 mod p, to see if you get q.
Example: Let q=2, p=17 so T = 2(2) mod 17 = 4 mod 17.
Here T=21 does not work, but T = 55 = 5(11), so z = 8 and the answer
then from
3k = 2( mod 17, is k = 11 mod 17.
Is there any use for such a technique?
James Harris
|
/* notes on JSH's "probabilistic square root mod p" */
Given prime p and quadratic residue q modulo p,
we seek k s.t. k^2 = q mod p.
JSH claims that the following procedure has 50%
chance of success:
Choose odd multiplier n to get T = 2q + np.
Factor T: f_1 * f_2 = 2q + np
[Here I simplify JSH's formulation, in that he
refers to the sum of factors f_1 + f_2 as 2z.]
Define z = f_1 + f_2 and k = z/3 mod p.
What has this to do with a square root of q?
Well, for k^2 = q mod p, it would require:
k^2 = (f_1^2 + 2 f_1*f_2 + f_2^2)/9 mod p
= (f_1^2 + 4 q + f_2^2)/9 mod p
5q = f_1^2 + f_2^2 mod p
A priori I can see no reason this should be
likely.
/* Example: Find k^2 = 3 mod 73 */
Since 3 is a quadratic residue mod 73 if and only if 73 is a quadratic
residue mod 3 (by quadratic reciprocity), and 73 = 1 mod 3, then 3 is
a quadratic residue mod 73. Also, 5q = 15.
Now taking:
n = 1: T = 6 + 73 = 79 prime
(1 + 79^2) mod 73 = 37
n = 3: T = 6 + 219 = 225 = 3*75 = 5*45 = 9*25 = 15 * 15
(1 + 225^2) mod 73 = 37
(9 + 75^2) mod 73 = 13
(25 + 45^2) mod 73 = 6
(81 + 25^2) mod 73 = 49
450 mod 73 = 12
n = 5: T = 6 + 365 = 371 = 7 * 53
(1 + 371^2) mod 73 = 37
(49 + 53^2) mod 73 = 11
n = 7: T = 6 + 511 = 517 = 11 * 47
(1 + 517^2) mod 73 = 37
(11^2 + 47^2) mod 73 = 67
n = 9: T = 6 + 657 = 663 = 3*13*17
(1 + 663^2) mod 73 = 37
(9 + 221^2) mod 73 = 13
(13^2 + 51^2) mod 73 = 69
(17^2 + 39^2) mod 73 = 58
n = 11: T = 6 + 803 = 809 prime
(1 + 809^2) mod 73 = 37
None of the smallish multipliers n = 1 to 11
gives a factorization T = f_1 * f_2 that
produces k such that k^2 = 3 mod 73.
regards, chip |
|
| Back to top |
|
|
| |
Ads |
Advertising
Sponsor
|
|
JSH
Guest
|
| Posted: Fri Jun 27, 2008 5:01 am Post subject: Re: JSH: Probabilistic quadratic residue solving |
|
|
On Jun 23, 7:46 pm, Chip Eastham <hardm...@gmail.com> wrote:
| Quote: |
On Jun 22, 10:26 am, JSH <jst...@gmail.com> wrote:
An off-shoot of my surrogate factoring research is a probabilistic
method to solve quadratic residues, as given
k^2 = q mod p
when p is an odd prime, and q is a quadratic residue modulo p, you
find k.
The technique requires introduction of a few additional variables
starting with T, where
T = 2q + np
where n is an odd natural number so you have T = 2q mod p, but T - 2q
is also forced to have p as a factor.
Next you find z, where with integer factors f_1 and f_2 where f_1*f_2
= T:
z = (f_1 + f_2)/2
and now finally you try for an answer for k, with
k = 3^{-1}(2z) mod p.
The method is probabilistic because if I've got the analysis right you
have a 50% probability of getting the right k, for each z that you
try. Checking is done by looking at k^2 mod p, to see if you get q.
Example: Let q=2, p=17 so T = 2(2) mod 17 = 4 mod 17.
Here T=21 does not work, but T = 55 = 5(11), so z = 8 and the answer
then from
3k = 2( mod 17, is k = 11 mod 17.
Is there any use for such a technique?
James Harris
/* notes on JSH's "probabilistic square root mod p" */
Given prime p and quadratic residue q modulo p,
we seek k s.t. k^2 = q mod p.
JSH claims that the following procedure has 50%
chance of success:
Choose odd multiplier n to get T = 2q + np.
Factor T: f_1 * f_2 = 2q + np
[Here I simplify JSH's formulation, in that he
refers to the sum of factors f_1 + f_2 as 2z.]
Define z = f_1 + f_2 and k = z/3 mod p.
What has this to do with a square root of q?
Well, for k^2 = q mod p, it would require:
k^2 = (f_1^2 + 2 f_1*f_2 + f_2^2)/9 mod p
= (f_1^2 + 4 q + f_2^2)/9 mod p
5q = f_1^2 + f_2^2 mod p
A priori I can see no reason this should be
likely.
/* Example: Find k^2 = 3 mod 73 */
Since 3 is a quadratic residue mod 73 if and only if 73 is a quadratic
residue mod 3 (by quadratic reciprocity), and 73 = 1 mod 3, then 3 is
a quadratic residue mod 73. Also, 5q = 15.
Now taking:
n = 1: T = 6 + 73 = 79 prime
(1 + 79^2) mod 73 = 37
n = 3: T = 6 + 219 = 225 = 3*75 = 5*45 = 9*25 = 15 * 15
(1 + 225^2) mod 73 = 37
(9 + 75^2) mod 73 = 13
(25 + 45^2) mod 73 = 6
(81 + 25^2) mod 73 = 49
450 mod 73 = 12
n = 5: T = 6 + 365 = 371 = 7 * 53
(1 + 371^2) mod 73 = 37
(49 + 53^2) mod 73 = 11
n = 7: T = 6 + 511 = 517 = 11 * 47
(1 + 517^2) mod 73 = 37
(11^2 + 47^2) mod 73 = 67
n = 9: T = 6 + 657 = 663 = 3*13*17
(1 + 663^2) mod 73 = 37
(9 + 221^2) mod 73 = 13
(13^2 + 51^2) mod 73 = 69
(17^2 + 39^2) mod 73 = 58
n = 11: T = 6 + 803 = 809 prime
(1 + 809^2) mod 73 = 37
None of the smallish multipliers n = 1 to 11
gives a factorization T = f_1 * f_2 that
produces k such that k^2 = 3 mod 73.
regards, chip
|
k = 21, so maybe k has to be coprime to q? But if so, why?
Did you try that at random or find it? Searching for a case that
wouldn't work?
___JSH |
|
| Back to top |
|
|
| |
Ads |
Advertising
Sponsor
|
|
JSH
Guest
|
| Posted: Sat Jun 28, 2008 12:09 am Post subject: Re: JSH: Probabilistic quadratic residue solving |
|
|
On Jun 26, 10:01 pm, JSH <jst...@gmail.com> wrote:
| Quote: |
On Jun 23, 7:46 pm, Chip Eastham <hardm...@gmail.com> wrote:
On Jun 22, 10:26 am, JSH <jst...@gmail.com> wrote:
An off-shoot of my surrogate factoring research is a probabilistic
method to solve quadratic residues, as given
k^2 = q mod p
when p is an odd prime, and q is a quadratic residue modulo p, you
find k.
The technique requires introduction of a few additional variables
starting with T, where
T = 2q + np
where n is an odd natural number so you have T = 2q mod p, but T - 2q
is also forced to have p as a factor.
Next you find z, where with integer factors f_1 and f_2 where f_1*f_2
= T:
z = (f_1 + f_2)/2
and now finally you try for an answer for k, with
k = 3^{-1}(2z) mod p.
The method is probabilistic because if I've got the analysis right you
have a 50% probability of getting the right k, for each z that you
try. Checking is done by looking at k^2 mod p, to see if you get q..
Example: Let q=2, p=17 so T = 2(2) mod 17 = 4 mod 17.
Here T=21 does not work, but T = 55 = 5(11), so z = 8 and the answer
then from
3k = 2( mod 17, is k = 11 mod 17.
Is there any use for such a technique?
James Harris
/* notes on JSH's "probabilistic square root mod p" */
Given prime p and quadratic residue q modulo p,
we seek k s.t. k^2 = q mod p.
JSH claims that the following procedure has 50%
chance of success:
Choose odd multiplier n to get T = 2q + np.
Factor T: f_1 * f_2 = 2q + np
[Here I simplify JSH's formulation, in that he
refers to the sum of factors f_1 + f_2 as 2z.]
Define z = f_1 + f_2 and k = z/3 mod p.
What has this to do with a square root of q?
Well, for k^2 = q mod p, it would require:
k^2 = (f_1^2 + 2 f_1*f_2 + f_2^2)/9 mod p
= (f_1^2 + 4 q + f_2^2)/9 mod p
5q = f_1^2 + f_2^2 mod p
A priori I can see no reason this should be
likely.
/* Example: Find k^2 = 3 mod 73 */
Since 3 is a quadratic residue mod 73 if and only if 73 is a quadratic
residue mod 3 (by quadratic reciprocity), and 73 = 1 mod 3, then 3 is
a quadratic residue mod 73. Also, 5q = 15.
Now taking:
n = 1: T = 6 + 73 = 79 prime
(1 + 79^2) mod 73 = 37
n = 3: T = 6 + 219 = 225 = 3*75 = 5*45 = 9*25 = 15 * 15
(1 + 225^2) mod 73 = 37
(9 + 75^2) mod 73 = 13
(25 + 45^2) mod 73 = 6
(81 + 25^2) mod 73 = 49
450 mod 73 = 12
n = 5: T = 6 + 365 = 371 = 7 * 53
(1 + 371^2) mod 73 = 37
(49 + 53^2) mod 73 = 11
n = 7: T = 6 + 511 = 517 = 11 * 47
(1 + 517^2) mod 73 = 37
(11^2 + 47^2) mod 73 = 67
n = 9: T = 6 + 657 = 663 = 3*13*17
(1 + 663^2) mod 73 = 37
(9 + 221^2) mod 73 = 13
(13^2 + 51^2) mod 73 = 69
(17^2 + 39^2) mod 73 = 58
n = 11: T = 6 + 803 = 809 prime
(1 + 809^2) mod 73 = 37
None of the smallish multipliers n = 1 to 11
gives a factorization T = f_1 * f_2 that
produces k such that k^2 = 3 mod 73.
regards, chip
k = 21, so maybe k has to be coprime to q? But if so, why?
|
Correction: k = 15.
| Quote: |
Did you try that at random or find it? Searching for a case that
wouldn't work?
|
I figured it out, as if T is a square then, of course, you can simply
take its square root to get k.
So you have to check if T is a square, which isn't a terrible thing as
if it is, then, of course, you're done anyway and that's not new.
What is new is a short-cut which can give you an answer much, much,
much faster in general then simply looking for a perfect square.
James Harris |
|
| Back to top |
|
|
| |
Ads |
Advertising
Sponsor
|
|
JSH
Guest
|
| Posted: Sat Jun 28, 2008 12:12 am Post subject: Re: JSH: Probabilistic quadratic residue solving |
|
|
On Jun 22, 7:26 am, JSH <jst...@gmail.com> wrote:
| Quote: |
An off-shoot of my surrogate factoring research is a probabilistic
method to solve quadratic residues, as given
k^2 = q mod p
when p is an odd prime, and q is a quadratic residue modulo p, you
find k.
The technique requires introduction of a few additional variables
starting with T, where
T = 2q + np
where n is an odd natural number so you have T = 2q mod p, but T - 2q
is also forced to have p as a factor.
|
Also as pointed out by an example from Chip Eastham in this thread, if
T is a perfect square, then you are, of course, done, as you can
simply take its square root!
So you continue only if T is not a perfect square.
| Quote: |
Next you find z, where with integer factors f_1 and f_2 where f_1*f_2
= T:
z = (f_1 + f_2)/2
and now finally you try for an answer for k, with
k = 3^{-1}(2z) mod p.
The method is probabilistic because if I've got the analysis right you
have a 50% probability of getting the right k, for each z that you
try. Checking is done by looking at k^2 mod p, to see if you get q.
|
Which is why it's a super advance on just finding T a square which is
the old tech.
The new tech is this kind of a trick that can greatly speed up the
process.
| Quote: |
Example: Let q=2, p=17 so T = 2(2) mod 17 = 4 mod 17.
Here T=21 does not work, but T = 55 = 5(11), so z = 8 and the answer
then from
3k = 2( mod 17, is k = 11 mod 17.
Is there any use for such a technique?
|
I'd think there should be for anyone who likes SPEED and wants to
solve a quadratic residue.
But maybe none of you do, or maybe mathematicians are not into the
best techniques--if one of their own doesn't find them.
As I've noted many times about a field that can't be the best so it
ignores the best.
James Harris |
|
| Back to top |
|
|
| |
Ads |
Advertising
Sponsor
|
|
Chip Eastham
Guest
|
| Posted: Sat Jun 28, 2008 2:45 am Post subject: Re: JSH: Probabilistic quadratic residue solving |
|
|
On Jun 27, 8:09 pm, JSH <jst...@gmail.com> wrote:
| Quote: |
On Jun 26, 10:01 pm, JSH <jst...@gmail.com> wrote:
On Jun 23, 7:46 pm, Chip Eastham <hardm...@gmail.com> wrote:
On Jun 22, 10:26 am, JSH <jst...@gmail.com> wrote:
An off-shoot of my surrogate factoring research is a probabilistic
method to solve quadratic residues, as given
k^2 = q mod p
when p is an odd prime, and q is a quadratic residue modulo p, you
find k.
The technique requires introduction of a few additional variables
starting with T, where
T = 2q + np
where n is an odd natural number so you have T = 2q mod p, but T - 2q
is also forced to have p as a factor.
Next you find z, where with integer factors f_1 and f_2 where f_1*f_2
= T:
z = (f_1 + f_2)/2
and now finally you try for an answer for k, with
k = 3^{-1}(2z) mod p.
The method is probabilistic because if I've got the analysis right you
have a 50% probability of getting the right k, for each z that you
try. Checking is done by looking at k^2 mod p, to see if you get q.
Example: Let q=2, p=17 so T = 2(2) mod 17 = 4 mod 17.
Here T=21 does not work, but T = 55 = 5(11), so z = 8 and the answer
then from
3k = 2( mod 17, is k = 11 mod 17.
Is there any use for such a technique?
James Harris
/* notes on JSH's "probabilistic square root mod p" */
Given prime p and quadratic residue q modulo p,
we seek k s.t. k^2 = q mod p.
JSH claims that the following procedure has 50%
chance of success:
Choose odd multiplier n to get T = 2q + np.
Factor T: f_1 * f_2 = 2q + np
[Here I simplify JSH's formulation, in that he
refers to the sum of factors f_1 + f_2 as 2z.]
Define z = f_1 + f_2 and k = z/3 mod p.
What has this to do with a square root of q?
Well, for k^2 = q mod p, it would require:
k^2 = (f_1^2 + 2 f_1*f_2 + f_2^2)/9 mod p
= (f_1^2 + 4 q + f_2^2)/9 mod p
5q = f_1^2 + f_2^2 mod p
A priori I can see no reason this should be
likely.
/* Example: Find k^2 = 3 mod 73 */
Since 3 is a quadratic residue mod 73 if and only if 73 is a quadratic
residue mod 3 (by quadratic reciprocity), and 73 = 1 mod 3, then 3 is
a quadratic residue mod 73. Also, 5q = 15.
Now taking:
n = 1: T = 6 + 73 = 79 prime
(1 + 79^2) mod 73 = 37
n = 3: T = 6 + 219 = 225 = 3*75 = 5*45 = 9*25 = 15 * 15
(1 + 225^2) mod 73 = 37
(9 + 75^2) mod 73 = 13
(25 + 45^2) mod 73 = 6
(81 + 25^2) mod 73 = 49
450 mod 73 = 12
n = 5: T = 6 + 365 = 371 = 7 * 53
(1 + 371^2) mod 73 = 37
(49 + 53^2) mod 73 = 11
n = 7: T = 6 + 511 = 517 = 11 * 47
(1 + 517^2) mod 73 = 37
(11^2 + 47^2) mod 73 = 67
n = 9: T = 6 + 657 = 663 = 3*13*17
(1 + 663^2) mod 73 = 37
(9 + 221^2) mod 73 = 13
(13^2 + 51^2) mod 73 = 69
(17^2 + 39^2) mod 73 = 58
n = 11: T = 6 + 803 = 809 prime
(1 + 809^2) mod 73 = 37
None of the smallish multipliers n = 1 to 11
gives a factorization T = f_1 * f_2 that
produces k such that k^2 = 3 mod 73.
regards, chip
k = 21, so maybe k has to be coprime to q? But if so, why?
Correction: k = 15.
Did you try that at random or find it? Searching for a case that
wouldn't work?
I figured it out, as if T is a square then, of course, you can simply
take its square root to get k.
So you have to check if T is a square, which isn't a terrible thing as
if it is, then, of course, you're done anyway and that's not new.
What is new is a short-cut which can give you an answer much, much,
much faster in general then simply looking for a perfect square.
James Harris
|
First, I didn't do any searching. This was the first
thing I tried, picking p = 73 because it's a prime
congruent to 1 mod 8 (the only cases for which a fast
deterministic method is unknown, so potentially where
room for improvement in a probabilistic method exists).
Second, I don't see the benefit of finding T is a square.
Yes, this gives a square root mod p for 2q, but not for q.
Here 15^2 = 225 = 6 = 2q mod p for q = 3 and p = 73.73.
How would this help find a square root for 3 mod 73? It
reduces the problem to finding a square root for 2 mod 73.
You were "right" with the answer 21^2 = 441 = 3 mod 73,
but I assume (since you showed no work) this answer was
not obtained by the probabilistic method you outlined.
regards, chip |
|
| Back to top |
|
|
| |
Ads |
Advertising
Sponsor
|
|
JSH
Guest
|
| Posted: Sat Jun 28, 2008 3:20 am Post subject: Re: JSH: Probabilistic quadratic residue solving |
|
|
On Jun 27, 7:45 pm, Chip Eastham <hardm...@gmail.com> wrote:
| Quote: |
On Jun 27, 8:09 pm, JSH <jst...@gmail.com> wrote:
On Jun 26, 10:01 pm, JSH <jst...@gmail.com> wrote:
On Jun 23, 7:46 pm, Chip Eastham <hardm...@gmail.com> wrote:
On Jun 22, 10:26 am, JSH <jst...@gmail.com> wrote:
An off-shoot of my surrogate factoring research is a probabilistic
method to solve quadratic residues, as given
k^2 = q mod p
when p is an odd prime, and q is a quadratic residue modulo p, you
find k.
The technique requires introduction of a few additional variables
starting with T, where
T = 2q + np
where n is an odd natural number so you have T = 2q mod p, but T - 2q
is also forced to have p as a factor.
Next you find z, where with integer factors f_1 and f_2 where f_1*f_2
= T:
z = (f_1 + f_2)/2
and now finally you try for an answer for k, with
k = 3^{-1}(2z) mod p.
The method is probabilistic because if I've got the analysis right you
have a 50% probability of getting the right k, for each z that you
try. Checking is done by looking at k^2 mod p, to see if you get q.
Example: Let q=2, p=17 so T = 2(2) mod 17 = 4 mod 17.
Here T=21 does not work, but T = 55 = 5(11), so z = 8 and the answer
then from
3k = 2( mod 17, is k = 11 mod 17.
Is there any use for such a technique?
James Harris
/* notes on JSH's "probabilistic square root mod p" */
Given prime p and quadratic residue q modulo p,
we seek k s.t. k^2 = q mod p.
JSH claims that the following procedure has 50%
chance of success:
Choose odd multiplier n to get T = 2q + np.
Factor T: f_1 * f_2 = 2q + np
[Here I simplify JSH's formulation, in that he
refers to the sum of factors f_1 + f_2 as 2z.]
Define z = f_1 + f_2 and k = z/3 mod p.
What has this to do with a square root of q?
Well, for k^2 = q mod p, it would require:
k^2 = (f_1^2 + 2 f_1*f_2 + f_2^2)/9 mod p
= (f_1^2 + 4 q + f_2^2)/9 mod p
5q = f_1^2 + f_2^2 mod p
A priori I can see no reason this should be
likely.
/* Example: Find k^2 = 3 mod 73 */
Since 3 is a quadratic residue mod 73 if and only if 73 is a quadratic
residue mod 3 (by quadratic reciprocity), and 73 = 1 mod 3, then 3 is
a quadratic residue mod 73. Also, 5q = 15.
Now taking:
n = 1: T = 6 + 73 = 79 prime
(1 + 79^2) mod 73 = 37
n = 3: T = 6 + 219 = 225 = 3*75 = 5*45 = 9*25 = 15 * 15
(1 + 225^2) mod 73 = 37
(9 + 75^2) mod 73 = 13
(25 + 45^2) mod 73 = 6
(81 + 25^2) mod 73 = 49
450 mod 73 = 12
n = 5: T = 6 + 365 = 371 = 7 * 53
(1 + 371^2) mod 73 = 37
(49 + 53^2) mod 73 = 11
n = 7: T = 6 + 511 = 517 = 11 * 47
(1 + 517^2) mod 73 = 37
(11^2 + 47^2) mod 73 = 67
n = 9: T = 6 + 657 = 663 = 3*13*17
(1 + 663^2) mod 73 = 37
(9 + 221^2) mod 73 = 13
(13^2 + 51^2) mod 73 = 69
(17^2 + 39^2) mod 73 = 58
n = 11: T = 6 + 803 = 809 prime
(1 + 809^2) mod 73 = 37
None of the smallish multipliers n = 1 to 11
gives a factorization T = f_1 * f_2 that
produces k such that k^2 = 3 mod 73.
regards, chip
k = 21, so maybe k has to be coprime to q? But if so, why?
Correction: k = 15.
Did you try that at random or find it? Searching for a case that
wouldn't work?
I figured it out, as if T is a square then, of course, you can simply
take its square root to get k.
So you have to check if T is a square, which isn't a terrible thing as
if it is, then, of course, you're done anyway and that's not new.
What is new is a short-cut which can give you an answer much, much,
much faster in general then simply looking for a perfect square.
James Harris
First, I didn't do any searching. This was the first
thing I tried, picking p = 73 because it's a prime
congruent to 1 mod 8 (the only cases for which a fast
deterministic method is unknown, so potentially where
room for improvement in a probabilistic method exists).
|
That's no the problem. q=3 was.
| Quote: |
Second, I don't see the benefit of finding T is a square.
Yes, this gives a square root mod p for 2q, but not for q.
Here 15^2 = 225 = 6 = 2q mod p for q = 3 and p = 73.73.
How would this help find a square root for 3 mod 73? It
reduces the problem to finding a square root for 2 mod 73.
You were "right" with the answer 21^2 = 441 = 3 mod 73,
but I assume (since you showed no work) this answer was
not obtained by the probabilistic method you outlined.
regards, chip
|
Nope, I went and looked for it. The problem is 3. Try another q with
p=73 that is a quadratic residue that is not divisible by 3 and see
what happens. Oh yeah, it took two things: p mod 3 = 1 and q=3 for
big problems to arise so you had a lucky set of choices, which isn't a
bad thing. I find the issue curious.
I am puzzling over why it's such a big deal.
___JSH |
|
| Back to top |
|
|
| |
Ads |
Advertising
Sponsor
|
|
JSH
Guest
|
| Posted: Sat Jun 28, 2008 3:45 am Post subject: Re: JSH: Probabilistic quadratic residue solving |
|
|
On Jun 27, 7:45 pm, Chip Eastham <hardm...@gmail.com> wrote:
| Quote: |
On Jun 27, 8:09 pm, JSH <jst...@gmail.com> wrote:
On Jun 26, 10:01 pm, JSH <jst...@gmail.com> wrote:
On Jun 23, 7:46 pm, Chip Eastham <hardm...@gmail.com> wrote:
On Jun 22, 10:26 am, JSH <jst...@gmail.com> wrote:
An off-shoot of my surrogate factoring research is a probabilistic
method to solve quadratic residues, as given
k^2 = q mod p
when p is an odd prime, and q is a quadratic residue modulo p, you
find k.
The technique requires introduction of a few additional variables
starting with T, where
T = 2q + np
where n is an odd natural number so you have T = 2q mod p, but T - 2q
is also forced to have p as a factor.
Next you find z, where with integer factors f_1 and f_2 where f_1*f_2
= T:
z = (f_1 + f_2)/2
and now finally you try for an answer for k, with
k = 3^{-1}(2z) mod p.
The method is probabilistic because if I've got the analysis right you
have a 50% probability of getting the right k, for each z that you
try. Checking is done by looking at k^2 mod p, to see if you get q.
Example: Let q=2, p=17 so T = 2(2) mod 17 = 4 mod 17.
Here T=21 does not work, but T = 55 = 5(11), so z = 8 and the answer
then from
3k = 2( mod 17, is k = 11 mod 17.
Is there any use for such a technique?
James Harris
/* notes on JSH's "probabilistic square root mod p" */
Given prime p and quadratic residue q modulo p,
we seek k s.t. k^2 = q mod p.
JSH claims that the following procedure has 50%
chance of success:
Choose odd multiplier n to get T = 2q + np.
Factor T: f_1 * f_2 = 2q + np
[Here I simplify JSH's formulation, in that he
refers to the sum of factors f_1 + f_2 as 2z.]
Define z = f_1 + f_2 and k = z/3 mod p.
What has this to do with a square root of q?
Well, for k^2 = q mod p, it would require:
k^2 = (f_1^2 + 2 f_1*f_2 + f_2^2)/9 mod p
= (f_1^2 + 4 q + f_2^2)/9 mod p
5q = f_1^2 + f_2^2 mod p
A priori I can see no reason this should be
likely.
/* Example: Find k^2 = 3 mod 73 */
Since 3 is a quadratic residue mod 73 if and only if 73 is a quadratic
residue mod 3 (by quadratic reciprocity), and 73 = 1 mod 3, then 3 is
a quadratic residue mod 73. Also, 5q = 15.
Now taking:
n = 1: T = 6 + 73 = 79 prime
(1 + 79^2) mod 73 = 37
n = 3: T = 6 + 219 = 225 = 3*75 = 5*45 = 9*25 = 15 * 15
(1 + 225^2) mod 73 = 37
(9 + 75^2) mod 73 = 13
(25 + 45^2) mod 73 = 6
(81 + 25^2) mod 73 = 49
450 mod 73 = 12
n = 5: T = 6 + 365 = 371 = 7 * 53
(1 + 371^2) mod 73 = 37
(49 + 53^2) mod 73 = 11
n = 7: T = 6 + 511 = 517 = 11 * 47
(1 + 517^2) mod 73 = 37
(11^2 + 47^2) mod 73 = 67
n = 9: T = 6 + 657 = 663 = 3*13*17
(1 + 663^2) mod 73 = 37
(9 + 221^2) mod 73 = 13
(13^2 + 51^2) mod 73 = 69
(17^2 + 39^2) mod 73 = 58
n = 11: T = 6 + 803 = 809 prime
(1 + 809^2) mod 73 = 37
None of the smallish multipliers n = 1 to 11
gives a factorization T = f_1 * f_2 that
produces k such that k^2 = 3 mod 73.
regards, chip
k = 21, so maybe k has to be coprime to q? But if so, why?
Correction: k = 15.
Did you try that at random or find it? Searching for a case that
wouldn't work?
I figured it out, as if T is a square then, of course, you can simply
take its square root to get k.
So you have to check if T is a square, which isn't a terrible thing as
if it is, then, of course, you're done anyway and that's not new.
What is new is a short-cut which can give you an answer much, much,
much faster in general then simply looking for a perfect square.
James Harris
First, I didn't do any searching. This was the first
thing I tried, picking p = 73 because it's a prime
congruent to 1 mod 8 (the only cases for which a fast
deterministic method is unknown, so potentially where
room for improvement in a probabilistic method exists).
Second, I don't see the benefit of finding T is a square.
Yes, this gives a square root mod p for 2q, but not for q.
Here 15^2 = 225 = 6 = 2q mod p for q = 3 and p = 73.73.
How would this help find a square root for 3 mod 73? It
reduces the problem to finding a square root for 2 mod 73.
You were "right" with the answer 21^2 = 441 = 3 mod 73,
but I assume (since you showed no work) this answer was
not obtained by the probabilistic method you outlined.
regards, chip
|
Try these equations for your special case:
If T mod 3 = 1, because p mod 3 = 1 and q is divisible by 3, then an
alternate set of equations can be used as then
T = 10q mod p
and
k = 19^{-1}(6z) mod p.
___JSH |
|
| Back to top |
|
|
| |
Ads |
Advertising
Sponsor
|
|
Dudly
Guest
|
| Posted: Sat Jun 28, 2008 7:15 am Post subject: Re: JSH: Probabilistic quadratic residue solving |
|
|
"JSH" <jstevh@gmail.com> wrote in message
news:4913aeb0-ae43-43e8-947e-426d2dbc87e3@l28g2000prd.googlegroups.com...
On Jun 26, 10:01 pm, JSH <jst...@gmail.com> wrote:
| Quote: |
On Jun 23, 7:46 pm, Chip Eastham <hardm...@gmail.com> wrote:
SNIP |
What is new is a short-cut which can give you an answer much, much,
much faster in general then simply looking for a perfect square.
try it out, this was solved in 2000,
http://www.alpertron.com.ar/ECM.HTM
| Quote: |
[ JSH, check it out! Dario already finished it. ]
|
James Harris |
|
| Back to top |
|
|
| |
Ads |
Advertising
Sponsor
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
199 Attacks blocked
Powered by phpBB © 2001, 2005 phpBB Group
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
