## Is there a quick method of doing this

Expand Messages
• I am wondering if there is a quick way to work out all numbers such that: x^2 = y mod(z) where x is any positive integer less than z? Kevin.
Message 1 of 11 , Jul 11, 2004
I am wondering if there is a quick way to work out all numbers such
that:

x^2 = y mod(z)

where x is any positive integer less than z?

Kevin.
• Hi Mark, Thanks for responding. So I have to go to floating point for this then? I do know both y and z, and the limits on x are that it must be less than z.
Message 2 of 11 , Jul 11, 2004
Hi Mark,

Thanks for responding.

So I have to go to floating point for this then?

I do know both y and z, and the limits on x are that it must be less
than z.

Just so you know, I am implementing an algorithm that finds the
smallest exponent in a given base such that a divides (b^n)-1. Whether
this will ever turn out to be useful or not, I have no idea. However,
the algorithm works, it's just pretty slow at the moment.

Best Regards,

Kevin.

> On Sunday, July 11, 2004, at 06:56 PM, Kevin Acres wrote:
> > I am wondering if there is a quick way to work out all numbers such
> > that:
> >
> > x^2 = y mod(z)
> >
> > where x is any positive integer less than z?
> >
> >
> > Kevin.
>
> If you know y and z, then you can use a discrete log.
>
>
>
• ... No, a discrete log can be easily written with the use of floating point. The following link explains discrete logs and few ways to code them.
Message 3 of 11 , Jul 11, 2004
On Sunday, July 11, 2004, at 07:31 PM, Kevin Acres wrote:

> Hi Mark,
>
> Thanks for responding.
>
> So I have to go to floating point for this then?
>
> I do know both y and z, and the limits on x are that it must be less
> than z.
>
> Just so you know, I am implementing an algorithm that finds the
> smallest exponent in a given base such that a divides (b^n)-1. Whether
> this will ever turn out to be useful or not, I have no idea. However,
> the algorithm works, it's just pretty slow at the moment.
>
>
> Best Regards,
>
> Kevin.

No, a discrete log can be easily written with the use of floating
point. The following link explains discrete logs and few ways to code
them.

--Mark
• ... I think the more significant point is that link, in section 3.5, explains in great detail how to compute square roots in Z[n].
Message 4 of 11 , Jul 11, 2004
On Sun, 11 Jul 2004, Mark Rodenkirch wrote:
> No, a discrete log can be easily written with the use of floating
> point. The following link explains discrete logs and few ways to code
> them.
>

I think the more significant point is that link, in section 3.5, explains
in great detail how to compute square roots in Z[n].
• Hi, One of my main problems here is that I haven t studied any maths for about 30 years now. So I ve a little bit of catching up to do. Having said that, I
Message 5 of 11 , Jul 12, 2004
Hi,

One of my main problems here is that I haven't studied any maths for about
30 years now. So I've a little bit of catching up to do.

Having said that, I noticed that I can take a shortcut to most of what I
wanted to do insomuch as I only need to calculate the instances of:

x^2 = 1 mod y

for x less than y

Obviously the trivial results are x = 1 and x = y-1, I just need to find
out how to determine the others (if any).

Regards,

Kevin.

At 03:47 PM 12/07/2004, Carl Devore wrote:
>On Sun, 11 Jul 2004, Mark Rodenkirch wrote:
> > No, a discrete log can be easily written with the use of floating
> > point. The following link explains discrete logs and few ways to code
> > them.
> >
>
>I think the more significant point is that link, in section 3.5, explains
>in great detail how to compute square roots in Z[n].
>
>
>
>
>Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
>The Prime Pages : http://www.primepages.org/
>
>
>
>
>
>
• ... There will never be any other solutions.
Message 6 of 11 , Jul 12, 2004
On Mon, 12 Jul 2004, Kevin Acres wrote:
> I only need to calculate the instances of:
> x^2 = 1 mod y
> Obviously the trivial results are x = 1 and x = y-1, I just need to find
> out how to determine the others (if any).

There will never be any other solutions.
• ... Do you really, really mean that? What is 4^2 mod 15? What is 11^2 mod 15? Explain your reasoning. I do, of course, know what is going on. It will be
Message 7 of 11 , Jul 12, 2004
On Mon, 2004-07-12 at 12:43, Carl Devore wrote:
> On Mon, 12 Jul 2004, Kevin Acres wrote:
> > I only need to calculate the instances of:
> > x^2 = 1 mod y
> > Obviously the trivial results are x = 1 and x = y-1, I just need to find
> > out how to determine the others (if any).
>
> There will never be any other solutions.

Do you really, really mean that?

What is 4^2 mod 15? What is 11^2 mod 15?

I do, of course, know what is going on. It will be educational for all
concerned if Carl and Kevin work it out for themselves.

Paul
• ... Since dashing off that rapid response, it s occurred to me that it would also be educational to work out why the Rabin cryptosystem works and why there are
Message 8 of 11 , Jul 12, 2004
On Mon, 2004-07-12 at 13:27, Paul Leyland wrote:
> On Mon, 2004-07-12 at 12:43, Carl Devore wrote:
> > On Mon, 12 Jul 2004, Kevin Acres wrote:
> > > I only need to calculate the instances of:
> > > x^2 = 1 mod y
> > > Obviously the trivial results are x = 1 and x = y-1, I just need to find
> > > out how to determine the others (if any).
> >
> > There will never be any other solutions.
>
> Do you really, really mean that?
>
> What is 4^2 mod 15? What is 11^2 mod 15?
>
>
>
> I do, of course, know what is going on. It will be educational for all
> concerned if Carl and Kevin work it out for themselves.

Since dashing off that rapid response, it's occurred to me that it would
also be educational to work out why the Rabin cryptosystem works and why
there are certain composite numbers that the Quadratic Sieve algorithm
can not factor.

Paul
• ... Of course I was wrong. I neglected the casea where y is not prime. In general, you must factor y.
Message 9 of 11 , Jul 12, 2004
On 12 Jul 2004, Paul Leyland wrote:
> On Mon, 2004-07-12 at 12:43, Carl Devore wrote:
> > On Mon, 12 Jul 2004, Kevin Acres wrote:
> > > I only need to calculate the instances of:
> > > x^2 = 1 mod y
> > > Obviously the trivial results are x = 1 and x = y-1, I just need to find
> > > out how to determine the others (if any).
> > There will never be any other solutions.
>
> Do you really, really mean that?
> What is 4^2 mod 15? What is 11^2 mod 15?

Of course I was wrong. I neglected the casea where y is not prime. In
general, you must factor y.
• ... Well done! Not only have you explained your mistake, you have done so in a manner that has given away the minimum necessary, thereby letting others work it
Message 10 of 11 , Jul 12, 2004
On Mon, 2004-07-12 at 17:48, Carl Devore wrote:

> > Do you really, really mean that?
> > What is 4^2 mod 15? What is 11^2 mod 15?
>
> Of course I was wrong. I neglected the casea where y is not prime. In
> general, you must factor y.

Well done!

Not only have you explained your mistake, you have done so in a manner
that has given away the minimum necessary, thereby letting others work
it out for themselves without too many clues.

Paul
• Hi, I ll explain what is happening and hence why the question. Since re-discovering Will s reverse algorithm I have been trying to implement a faster
Message 11 of 11 , Jul 12, 2004
Hi,

I'll explain what is happening and hence why the question.

Since re-discovering Will's 'reverse algorithm' I have been trying to
implement a faster version. Although I have been re-creating the
smallest a^n - 1 that is divisible by a given number in less than a
second for a^n-1 up to about 2^50,000,000 - 1.

My latest attempt was to build a binary tree that reversed the trial
division method. i.e. start up with x^2 = 1 mod y and work up from
there.

Then I realised that for non-primes I was getting four entries in the
first level of the tree. Notably x = 1 and x = y -1.

Looking at specifics I noticed that the first level for 2047 gave me
1, 622, 1425 and 2046. A little investigation showed me that gcd
(2047, 622+1) gave me 89 and gcd(2047, 622-1) gave me 23 or the
factors of 2047.

This tends to suggest that I've just re-arrived at the factoring
problem from a different direction.

But, being a novice at this, it was interesting whilst it lasted :-)

Kevin.

> On Mon, 2004-07-12 at 13:27, Paul Leyland wrote:
> > On Mon, 2004-07-12 at 12:43, Carl Devore wrote:
> > > On Mon, 12 Jul 2004, Kevin Acres wrote:
> > > > I only need to calculate the instances of:
> > > > x^2 = 1 mod y
> > > > Obviously the trivial results are x = 1 and x = y-1, I just
need to find
> > > > out how to determine the others (if any).
> > >
> > > There will never be any other solutions.
> >
> > Do you really, really mean that?
> >
> > What is 4^2 mod 15? What is 11^2 mod 15?
> >
> >
> >
> > I do, of course, know what is going on. It will be educational
for all
> > concerned if Carl and Kevin work it out for themselves.
>
> Since dashing off that rapid response, it's occurred to me that it
would
> also be educational to work out why the Rabin cryptosystem works and
why
> there are certain composite numbers that the Quadratic Sieve
algorithm
> can not factor.
>
>
> Paul
>
>
>
>
> ------------------------ Yahoo! Groups Sponsor --------------------~-
->
> Yahoo! Domains - Claim yours for only \$14.70
> http://us.click.yahoo.com/Z1wmxD/DREIAA/yQLSAA/8HYolB/TM
> --------------------------------------------------------------------
~->
>
> Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
> The Prime Pages : http://www.primepages.org/
>
>