Hey, can you help me with these questions? If you need longer time please tell me. Ignore the first question cuz you've helped me. Thanks in advance.

 

 

Homework 5
CSE/MATH 467 Due: 23 September, 2016 1. (Coding problem from last week) Write fast exponentiation code and find
ten 10-digit probable primes (with respect to base 2).
13 2. a) Determine 1313 %10.
13
b) Determine 1313 %15.
3. Recall that we formulated Garner’s fast recursive general Chinese Remainder Theorem in the following way:
Input:
Moduli m1 , . . . , mr with gcd(mi , mj ) = 1 when i < j.
Representatives a1 , . . . , ar ∈ Z
Algorithm: Define recursively Ak (kth interpolation) and wk (kth weight) by
the following:
Intialization:
• w1 : = 0.
• w1 : = A1 : = a1 %m1 .
Recursion:
• wk+1 : = (ak+1 − Ak )(m1 · · · mk )∗ %mk+1
• Ak+1 : = Ak + (wk+1 m1 · · · mk ),
where (m1 · · · mk )(m1 · · · mk )∗ ≡ 1 mod mk+1 .
A. Show by induction on r that Ar = w1 +w2 m1 +· · ·+wr m1 . . . mr−1 satisfies
the system of congruences
x ≡ a1
..
.
x ≡ ar mod m1
mod mr B. At most how many multiplications modulo mk are actually involved in the
kth step if we take care to keep the sizes of numbers down? (Ignore those
coming from multiprecision considerations and from the Knuth algorithm to
compute multiplicative inverses modulo mk .) 4. Let p and q be odd primes with difference δ = p − q > 0 and product
n = pq.
√
(a) Show that the Fermat factorization method involves (p + q)/2 − d ne
increases in x to find x and y such that n = x2 − y 2 .
(b) Show that



p+q √
p+q √
1
− pq
+ pq = δ 2 .
2
2
4
(c) Assume that δ is so much smaller than p that we can consider (p+q)/2 ≈
√
p and pq ≈ p. Show that then


δ2
p+q √
− pq ≈ .
2
8p
2 (d) Suppose that p and q are 100-digit primes (so that p, q ≈ 1099 ) and
p − q ≈ 1080 so the most significant 19 or 20 digits are the same. Show
that the Fermat algorithm takes approximately 1060 increases in x.
(e) If p and q are 100-digit primes with p − q ≈ 1050 , show that the Fermat
method finds the factorization with very few increases in x.
5. We showed in class that if m, n ∈ N are relatively prime, then φ(mn) =
φ(m)φ(n). Prove by careful induction that if m1 , . . . , mr are pair-wise relatively prime positive integers, then φ(m1 · mr ) = φ(m1 ) · · · φ(mr ). You may
take r = 2 as the base case.

• 1492575323-hw05 1.pdf

ComputerScienceExpert

(11)

Status NEW Posted 19 Apr 2017 04:04 AM My Price 8.00

-----------

Attachments

file 1492575325-Solutions file 2.docx preview (51 words )

H-----------ell-----------o S-----------ir/-----------Mad-----------am ----------- Th-----------ank----------- yo-----------u f-----------or -----------you-----------r i-----------nte-----------res-----------t a-----------nd -----------buy-----------ing----------- my----------- po-----------ste-----------d s-----------olu-----------tio-----------n. -----------Ple-----------ase----------- pi-----------ng -----------me -----------on -----------cha-----------t I----------- am----------- on-----------lin-----------e o-----------r i-----------nbo-----------x m-----------e a----------- me-----------ssa-----------ge -----------I w-----------ill----------- be----------- qu-----------ick-----------ly -----------onl-----------ine----------- an-----------d g-----------ive----------- yo-----------u e-----------xac-----------t f-----------ile----------- an-----------d t-----------he -----------sam-----------e f-----------ile----------- is----------- al-----------so -----------sen-----------t t-----------o y-----------our----------- em-----------ail----------- th-----------at -----------is -----------reg-----------ist-----------ere-----------d o-----------n -----------THI-----------S W-----------EBS-----------ITE-----------. ----------- Th-----------ank----------- yo-----------u -----------

Not Rated(0)

• Buy Answer