Community

Visit the AoPS Book Store.
Login Register Memberlist Search AoPS Blogs Contests Galleries Forum Index
The time now is Sun Nov 22, 2009 8:55 pm
All times are UTC - 8
View posts since last visit
View unanswered posts
Chinese Remainder Theorem
Moderators: High School Olympiad Moderators, amfulger, Arne, darij grinberg, freemind, harazi, Megus, N.T.TUAN, orl, pbornsztein, ZetaX
Post new topic   Reply to topic View previous topicView next topic
2 Posts • Page 1 of 1
Author Message
mat12
New Member
New Member

Offline
Joined: 12 Feb 2005
Posts: 8
United States

To rate posts you must be logged in
#1
Chinese Remainder Theorem

I am trying to work on this problem..

A company wishes to permit only 2 people working together to be able to decode a message circulated
among a group of three people.The message is a number somewhere between
30 and 240.The company issues primes 13,19 and 23 to employees Alice,Bob and carol. The number will be given
mod these primes to each employee .If Alice gets a 6, Bob a 9, Carol a 8, then what was the message.

b)How could the company modify the scheme, so that all three people would have to be willing to share the information in order for it
to be decoded? similarly ,

c) How could the company modify the scheme so that only if r people out of n people are to be willing to share the information can it be decoded.

------ This is what I tried to do .........

x = 6mod13
x = 9mod19
x = 8mod23

M=5681
m1=13
m2=19
m3=23

But the question says only 2 people can work together.. How to proceed ?.
how to solve for a) and b)

Anyone can provide some help?..

Thank you

mat

PostPosted: Mon Feb 14, 2005 6:03 pm  Back to top 
  ProfilePMYM
RobertuX
Poincare Conjecture
Poincare Conjecture


Offline
Joined: 03 Feb 2005
Posts: 201
Location: == MADRID ==
Spain

To rate posts you must be logged in
#2
Re: Chinese Remainder Theorem

mat12 wrote:
I am trying to work on this problem..

A company wishes to permit only 2 people working together to be able to decode a message circulated
among a group of three people.The message is a number somewhere between
30 and 240.The company issues primes 13,19 and 23 to employees Alice,Bob and carol. The number will be given
mod these primes to each employee .If Alice gets a 6, Bob a 9, Carol a 8, then what was the message.

b)How could the company modify the scheme, so that all three people would have to be willing to share the information in order for it
to be decoded? similarly ,

c) How could the company modify the scheme so that only if r people out of n people are to be willing to share the information can it be decoded.

------ This is what I tried to do .........

x = 6mod13
x = 9mod19
x = 8mod23

M=5681
m1=13
m2=19
m3=23

But the question says only 2 people can work together.. How to proceed ?.
how to solve for a) and b)

Anyone can provide some help?..

Thank you

mat

Ok, I give you a tip and I hope you can solve, the idea is if x=a\ mod \ p and x=b \ mod \ q with ((p,q)=1 do the following, you know (p,q)=1 so, you need to find the coefficients of the bezout identity of (p,q), I mean, \alpha and \beta integers such that \alpha p+\beta q=1, in the case of 13 and 19, 3*19-2*19=1, and then
x=a+Dp=b+Eq \ \Rightarrow \ b-a=Dp-Eq \stackrel{(IDEA)}=(b-a)[\alpha p+\beta q]=Dp-Eq \ \Rightarrow \
[(b-a)\alpha -D]p=[(a-b...
then you can continue with this new equation and the following because if (p,q)=1 and (p,r)=1 and (q,r)=1 then (pq,r)=1, so again you need to find bezout identity and if at the end x=A\ mod \ (pqr) and D\le x<U then you get all the possible values, please, if you need some remark, say to me.

Best regards.
RX the Crazy Math
_________________
RobertuX against the PEOPLE WHO try to make other people to HATES Science

PostPosted: Wed Feb 16, 2005 12:14 am  Back to top 
  ProfilePMWWWAIMBlog
Display posts from previous:   Sort by:   
2 Posts • Page 1 of 1
Post new topic   Reply to topic View previous topicView next topic
Jump to:  

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
You cannot attach files in this forum
You can download files in this forum
You cannot post calendar events in this forum


© Copyright 2008 AoPS Incorporated. All Rights Reserved. • FoundationPrivacyContact Us