## A community for students. Sign up today

Here's the question you clicked on:

## myininaya 3 years ago 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

• This Question is Closed
1. satellite73

i can't even read this what class?

2. myininaya

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

3. satellite73

yeah well i cannot read what it says. good luck

4. myininaya

http://www.cacr.math.uwaterloo.ca/hac/ its in chapter 11 on page 473 at the bottom

5. myininaya

;p;

6. myininaya

lol*

7. myininaya

i wonder if james or zarkon could do it

8. myininaya

oh its zarkon lol

9. satellite73

good luck!

10. KingGeorge

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.

11. Zarkon

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

12. myininaya

i don't see this (pq)^2 part

13. myininaya

george what kind of math have you had?

14. Zarkon

${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$

15. myininaya

ok i see

16. myininaya

you are so smart to notice the first two values will only matter since n mod n is like totally 0 thanks zarkon

17. KingGeorge

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

18. Zarkon

no problem :)

19. myininaya

is there any number theory in abstract algebra i can't remember

20. KingGeorge

not very much. I'm taking intro to number theory, and cryptography next semester.

21. myininaya

i like cryptography

22. myininaya

number theory is so cool and interesting to me although my skills suck right now

23. KingGeorge

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.

24. myininaya

i like these math puzzles

25. myininaya

differential equations is not as fun to me but i do like the remedial kind lol

26. myininaya

zarkon do you think there is hope for my brain?

27. KingGeorge

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.

28. Zarkon

there is!

29. myininaya

i feel like i'm trapped inside with an apes' brain

30. Zarkon

A very smart ape ;)

31. myininaya

thanks i take that as a compliment

32. Zarkon

If you want a fun class...Take a course in measure theoretic probability theory.

33. myininaya

he says that because he is a stat nerd

34. KingGeorge

I don't think my school has that class...

35. myininaya

my doesn't either

36. Zarkon

or a class in stochastic processes

37. Zarkon

sometimes it will fall under the title of applied probability

38. myininaya

i think they might have that

39. myininaya

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

40. KingGeorge

I'm personally more of an algebra person. Stats was interesting at first, but then it got boring.

41. myininaya

There are some cool things though in stat i do admit

42. Zarkon

There is plenty of really nice mathematics in statistics

43. KingGeorge

It was the same with calculus for me. Interesting at first, and then it just stopped interesting me.

44. Zarkon

A lot of multivariate calculus and matrix theory

45. myininaya

zarkon can i ask another question

46. myininaya

this is my last problem with this proof...

47. Zarkon

ok

48. myininaya

omg never i got it lol

49. myininaya

i mean nvm

50. myininaya

i was typing it all out then i realized oh yeah lol

51. Zarkon

ok :)

52. myininaya

ok i feel good about this proof thanks for all your help

53. Zarkon

good...no problem

#### Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy