myininaya
I have the following information:
\[n=p^2q\]
\[k \ge 4\]
\[0<v<n\]
\[0 \le x < pq\]
\[y=\lceil \frac{(v-x^k) \mod n}{pq} \rceil \cdot (kx^{k-1})^{-1} \mod p\]
I want to show:
\[\sum_{i=0}^{k}\left(\begin{matrix} k \\ i \end{matrix}\right) x^{k-1}(ypq)^i \equiv x^k+kypqx^{k-1}\]
the congruence is mod n
Delete
Share
This Question is Closed
anonymous
Best Response
You've already chosen the best response.
0
i can't even read this
what class?
myininaya
Best Response
You've already chosen the best response.
0
i made a mistake
\[\sum_{i=0}^{k}\left(\begin{matrix} k \\ i \end{matrix}\right) x^{k-i}(ypq)^i \equiv x^k+kypqx^{k-1}\]
I'm trying to follow a proof
but i don't know how they got from that one part to the other part
anonymous
Best Response
You've already chosen the best response.
0
yeah well i cannot read what it says. good luck
myininaya
Best Response
You've already chosen the best response.
0
;p;
myininaya
Best Response
You've already chosen the best response.
0
lol*
myininaya
Best Response
You've already chosen the best response.
0
i wonder if james or zarkon could do it
myininaya
Best Response
You've already chosen the best response.
0
oh its zarkon lol
anonymous
Best Response
You've already chosen the best response.
0
good luck!
KingGeorge
Best Response
You've already chosen the best response.
0
ask me next semester when I've taken cryptography, and I might be able to help you, but right now, I haven't got a clue.
Zarkon
Best Response
You've already chosen the best response.
2
only the first two values of i will matter (i=0,1)
for i>1
you have a \((pq)^2\) part which is \(p^2qq=nq\) which is zero nod n
myininaya
Best Response
You've already chosen the best response.
0
i don't see this (pq)^2 part
myininaya
Best Response
You've already chosen the best response.
0
george what kind of math have you had?
Zarkon
Best Response
You've already chosen the best response.
2
\[{k\choose i}x^{k-1}(ypq)^i\]
for \(i\ge2\)
\[{k\choose i}x^{k-1}(ypq)^i={k\choose i}x^{k-1}(y^i)(pq)^{i-2}p^2qq\]
\[=\left({k\choose i}x^{k-1}(y^i)(pq)^{i-2}q\right)\times n\]
myininaya
Best Response
You've already chosen the best response.
0
ok i see
myininaya
Best Response
You've already chosen the best response.
0
you are so smart to notice the first two values will only matter since n mod n is like totally 0
thanks zarkon
KingGeorge
Best Response
You've already chosen the best response.
0
I've only had a year and a half of college level math so far, so that means, calc 1-3, lin. algebra, abstract algebra, and analysis
Zarkon
Best Response
You've already chosen the best response.
2
no problem :)
myininaya
Best Response
You've already chosen the best response.
0
is there any number theory in abstract algebra i can't remember
KingGeorge
Best Response
You've already chosen the best response.
0
not very much. I'm taking intro to number theory, and cryptography next semester.
myininaya
Best Response
You've already chosen the best response.
0
i like cryptography
myininaya
Best Response
You've already chosen the best response.
0
number theory is so cool and interesting to me
although my skills suck right now
KingGeorge
Best Response
You've already chosen the best response.
0
It certainly sounds fun. I'm definitely enjoying my abstract algebra class right now. We had the barest hints of some number theory in discrete math so I'm not completely helpless.
myininaya
Best Response
You've already chosen the best response.
0
i like these math puzzles
myininaya
Best Response
You've already chosen the best response.
0
differential equations is not as fun to me but i do like the remedial kind lol
myininaya
Best Response
You've already chosen the best response.
0
zarkon do you think there is hope for my brain?
KingGeorge
Best Response
You've already chosen the best response.
0
From my experience, I don't like differential equations very much. Granted, I've never had a full course in it, but it just isn't my thing.
Zarkon
Best Response
You've already chosen the best response.
2
there is!
myininaya
Best Response
You've already chosen the best response.
0
i feel like i'm trapped inside with an apes' brain
Zarkon
Best Response
You've already chosen the best response.
2
A very smart ape ;)
myininaya
Best Response
You've already chosen the best response.
0
thanks i take that as a compliment
Zarkon
Best Response
You've already chosen the best response.
2
If you want a fun class...Take a course in measure theoretic probability theory.
myininaya
Best Response
You've already chosen the best response.
0
he says that because he is a stat nerd
KingGeorge
Best Response
You've already chosen the best response.
0
I don't think my school has that class...
myininaya
Best Response
You've already chosen the best response.
0
my doesn't either
Zarkon
Best Response
You've already chosen the best response.
2
or a class in stochastic processes
Zarkon
Best Response
You've already chosen the best response.
2
sometimes it will fall under the title of applied probability
myininaya
Best Response
You've already chosen the best response.
0
i think they might have that
myininaya
Best Response
You've already chosen the best response.
0
i always had a 10 foot pole when it came to statistics
i only had to put it down when the course in stat was required
KingGeorge
Best Response
You've already chosen the best response.
0
I'm personally more of an algebra person. Stats was interesting at first, but then it got boring.
myininaya
Best Response
You've already chosen the best response.
0
There are some cool things though in stat i do admit
Zarkon
Best Response
You've already chosen the best response.
2
There is plenty of really nice mathematics in statistics
KingGeorge
Best Response
You've already chosen the best response.
0
It was the same with calculus for me. Interesting at first, and then it just stopped interesting me.
Zarkon
Best Response
You've already chosen the best response.
2
A lot of multivariate calculus and matrix theory
myininaya
Best Response
You've already chosen the best response.
0
zarkon can i ask another question
myininaya
Best Response
You've already chosen the best response.
0
this is my last problem with this proof...
Zarkon
Best Response
You've already chosen the best response.
2
ok
myininaya
Best Response
You've already chosen the best response.
0
omg never i got it lol
myininaya
Best Response
You've already chosen the best response.
0
i mean nvm
myininaya
Best Response
You've already chosen the best response.
0
i was typing it all out then i realized oh yeah lol
Zarkon
Best Response
You've already chosen the best response.
2
ok :)
myininaya
Best Response
You've already chosen the best response.
0
ok i feel good about this proof thanks for all your help
Zarkon
Best Response
You've already chosen the best response.
2
good...no problem