How is this true!

Expand Messages
• Hi, Let p & q be primes such that q devides p-1. I want to find r & x when I know y, t in the following equation. y = r(x+t) mod q, Here, r,x,t all belong to
Message 1 of 8 , May 30, 2002
• 0 Attachment
Hi,

Let p & q be primes such that q devides p-1.
I want to find r & x when I know y, t in the following equation.

y = r(x+t) mod q,

Here, r,x,t all belong to Zq* { multiplicative group}

I came to know that there are totally p-1 pairs of keys to the equation. so the probablity for finding x & r is : 1/p-1.

How is this true? I want to know the detailed explanation.

Thanks,
Lovebharath

---------------------------------
Do You Yahoo!?
Yahoo! - Official partner of 2002 FIFA World Cup

[Non-text portions of this message have been removed]
• ... So if you fix q then you ve not uniquely defined p. ... So you ve fixed q, then? ... But p doesn t have a uniquely defined value, as as yet indeterminate.
Message 2 of 8 , May 31, 2002
• 0 Attachment
--- bharath ERakajj <lovebharath@...> wrote:
>
> Hi,
>
> Let p & q be primes such that q devides p-1.

So if you fix q then you've not uniquely defined p.

> I want to find r & x when I know y, t in the following equation.
>
> y = r(x+t) mod q,
>
> Here, r,x,t all belong to Zq* { multiplicative group}

So you've fixed q, then?

> I came to know that there are totally p-1 pairs of keys to the
> equation. so the probablity for finding x & r is : 1/p-1.

But p doesn't have a uniquely defined value, as as yet indeterminate.

Phil

=====
--
"One cannot delete the Web browser from KDE without
losing the ability to manage files on the user's own
hard disk." - Prof. Stuart E Madnick, MIT.
So called "expert" witness for Microsoft. 2002/05/02

__________________________________________________
Do You Yahoo!?
Yahoo! - Official partner of 2002 FIFA World Cup
http://fifaworldcup.yahoo.com
• Infact I also expected the same way .. that is, there must be q-1 pairs of solutions .. but I was surprised when I found : There are totally p-1 pairs of keys
Message 3 of 8 , Jun 2, 2002
• 0 Attachment
Infact I also expected the same way .. that is, there must be q-1 pairs of solutions .. but I was surprised when I found :
"There are totally p-1 pairs of keys to the equation. so the probablity for finding x & r is : 1/p-1. "

So I asked to help me .. So my problem is still a problem (which I am noting down here again) ..

+++++++++++++++++++++++++++++++++
Let p & q be primes such that q devides p-1.
I want to find r & x when I know y, t in the following equation.

y = r(x+t) mod q,

Here, r,x,t all belong to Zq* { multiplicative group}

I came to know that there are totally p-1 pairs of keys to the equation. so the probablity for finding x & r is : 1/p-1.

How is this true? I want to know the detailed explanation. +++++++++++++++++++++++++++++++++++++++

Thanks,
Bharath

Chris Nash <chris_nash@...> wrote: Hi there

>I want to find r & x when I know y, t in the following equation.
>y = r(x+t) mod q,

For each value of r in Zq*, there is a unique s such that

rs=1 mod q

Multiply through the equation by s and so

x=ys-t

Hence for each of the q-1 values of r in Zq*, there is a single
solution for x.

Hope that helps

Chris Nash
Lexington KY
UNITED STATES

---------------------------------
Do You Yahoo!?
Yahoo! - Official partner of 2002 FIFA World Cup

[Non-text portions of this message have been removed]
• ... a) And what is your process of finding the pairs. Chris Nash s method generates one and exactly one x per r. There s no need to go out and find
Message 4 of 8 , Jun 2, 2002
• 0 Attachment
--- bharath ERakajj <lovebharath@...> wrote:
>
> Infact I also expected the same way .. that is, there must be q-1
> pairs of solutions .. but I was surprised when I found :
> "There are totally p-1 pairs of keys to the equation. so the
> probablity for finding x & r is : 1/p-1. "

a) And what is your process of "finding" the pairs. Chris Nash's
method generates one and exactly one x per r. There's no need to go
out and find solutions, simply turn the handle.
b) Likewise where do you think "probablity" enter into things?
c) What is gcd(y,t)?
d) 1/p-1 means (1/p)-1, not 1/(p-1).
e) When you say "q divides p-1" you are saying "q divides into p-1",
or "q|p-1". That is different from "q is divisible by p-1" or
"p-1|q". You mean the latter.

Phil

=====
--
"One cannot delete the Web browser from KDE without
losing the ability to manage files on the user's own
hard disk." - Prof. Stuart E Madnick, MIT.
So called "expert" witness for Microsoft. 2002/05/02

__________________________________________________
Do You Yahoo!?
Yahoo! - Official partner of 2002 FIFA World Cup
http://fifaworldcup.yahoo.com
• ... So 1/p-1 means (1/p)-1, but q|p-1 means q|(p-1)? Jon Perry perry@globalnet.co.uk http://www.users.globalnet.co.uk/~perry/maths BrainBench MVP for HTML and
Message 5 of 8 , Jun 4, 2002
• 0 Attachment
>1/p-1 means (1/p)-1, not 1/(p-1).
>When you say "q divides p-1" you are saying "q divides into p-1",
>or "q|p-1". That is different from "q is divisible by p-1" or
>"p-1|q". You mean the latter.

So 1/p-1 means (1/p)-1, but q|p-1 means q|(p-1)?

Jon Perry
perry@...
http://www.users.globalnet.co.uk/~perry/maths
BrainBench MVP for HTML and JavaScript
http://www.brainbench.com

-----Original Message-----
From: Phil Carmody [mailto:thefatphil@...]
Sent: 03 June 2002 06:56
To: bharath ERakajj; numbertheory@yahoogroups.com;
cryptography@yahoogroups.com; maththeorists@yahoogroups.com
Subject: Re: [PrimeNumbers] Re: How is this true!

--- bharath ERakajj <lovebharath@...> wrote:
>
> Infact I also expected the same way .. that is, there must be q-1
> pairs of solutions .. but I was surprised when I found :
> "There are totally p-1 pairs of keys to the equation. so the
> probablity for finding x & r is : 1/p-1. "

a) And what is your process of "finding" the pairs. Chris Nash's
method generates one and exactly one x per r. There's no need to go
out and find solutions, simply turn the handle.
b) Likewise where do you think "probablity" enter into things?
c) What is gcd(y,t)?
d) 1/p-1 means (1/p)-1, not 1/(p-1).
e) When you say "q divides p-1" you are saying "q divides into p-1",
or "q|p-1". That is different from "q is divisible by p-1" or
"p-1|q". You mean the latter.

Phil

=====
--
"One cannot delete the Web browser from KDE without
losing the ability to manage files on the user's own
hard disk." - Prof. Stuart E Madnick, MIT.
So called "expert" witness for Microsoft. 2002/05/02

__________________________________________________
Do You Yahoo!?
Yahoo! - Official partner of 2002 FIFA World Cup
http://fifaworldcup.yahoo.com

Unsubscribe by an email to: primenumbers-unsubscribe@egroups.com
The Prime Pages : http://www.primepages.org

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
• ... Yup. One is multiplicative in precedence, the other is effectively equality/relational in precedence. It may superficially it looks like it s to do with
Message 6 of 8 , Jun 4, 2002
• 0 Attachment
--- Jon Perry <perry@...> wrote:
> >1/p-1 means (1/p)-1, not 1/(p-1).
> >When you say "q divides p-1" you are saying "q divides into p-1",
> >or "q|p-1". That is different from "q is divisible by p-1" or
> >"p-1|q". You mean the latter.
>
> So 1/p-1 means (1/p)-1, but q|p-1 means q|(p-1)?

Yup.

One is multiplicative in precedence, the other is effectively
equality/relational in precedence. It may superficially it looks like
it's to do with one of the multiplicative family of operators, but
no, it's a logical predicate, indicating some kind of equality,
namely (p-1)%q == 0 in C terms.

Look at a few papers and books, you'll almost always see it used with
a precedence similar to an equality/relational operator.

Phil

=====
--
"One cannot delete the Web browser from KDE without
losing the ability to manage files on the user's own
hard disk." - Prof. Stuart E Madnick, MIT.
So called "expert" witness for Microsoft. 2002/05/02

__________________________________________________
Do You Yahoo!?
Yahoo! - Official partner of 2002 FIFA World Cup
http://fifaworldcup.yahoo.com
• Surely then p-1|q implies p - (1|q)? Jon Perry perry@globalnet.co.uk http://www.users.globalnet.co.uk/~perry/maths BrainBench MVP for HTML and JavaScript
Message 7 of 8 , Jun 4, 2002
• 0 Attachment
Surely then p-1|q implies p - (1|q)?

Jon Perry
perry@...
http://www.users.globalnet.co.uk/~perry/maths
BrainBench MVP for HTML and JavaScript
http://www.brainbench.com

-----Original Message-----
From: Phil Carmody [mailto:thefatphil@...]
Sent: 04 June 2002 13:30
Subject: RE: [PrimeNumbers] Re: How is this true!

--- Jon Perry <perry@...> wrote:
> >1/p-1 means (1/p)-1, not 1/(p-1).
> >When you say "q divides p-1" you are saying "q divides into p-1",
> >or "q|p-1". That is different from "q is divisible by p-1" or
> >"p-1|q". You mean the latter.
>
> So 1/p-1 means (1/p)-1, but q|p-1 means q|(p-1)?

Yup.

One is multiplicative in precedence, the other is effectively
equality/relational in precedence. It may superficially it looks like
it's to do with one of the multiplicative family of operators, but
no, it's a logical predicate, indicating some kind of equality,
namely (p-1)%q == 0 in C terms.

Look at a few papers and books, you'll almost always see it used with
a precedence similar to an equality/relational operator.

Phil

=====
--
"One cannot delete the Web browser from KDE without
losing the ability to manage files on the user's own
hard disk." - Prof. Stuart E Madnick, MIT.
So called "expert" witness for Microsoft. 2002/05/02

__________________________________________________
Do You Yahoo!?
Yahoo! - Official partner of 2002 FIFA World Cup
http://fifaworldcup.yahoo.com

Unsubscribe by an email to: primenumbers-unsubscribe@egroups.com
The Prime Pages : http://www.primepages.org

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
• ... What planet are you on, Jon? What types are the two operators (i.e. what types do they operate on, and what type do they evaluate to)? Sheesh. Phil =====
Message 8 of 8 , Jun 4, 2002
• 0 Attachment
--- Jon Perry <perry@...> wrote:
> Surely then p-1|q implies p - (1|q)?

What planet are you on, Jon?

What types are the two operators (i.e. what types do they operate on,
and what type do they evaluate to)?

Sheesh.

Phil

=====
--
"One cannot delete the Web browser from KDE without
losing the ability to manage files on the user's own
hard disk." - Prof. Stuart E Madnick, MIT.
So called "expert" witness for Microsoft. 2002/05/02

__________________________________________________
Do You Yahoo!?
Yahoo! - Official partner of 2002 FIFA World Cup
http://fifaworldcup.yahoo.com
Your message has been successfully submitted and would be delivered to recipients shortly.