In this assignment, you need to implement Qins Algorithm (from Lecture Note 2) and RSA operations using Java or C/C++ (you need to use the package GMP for C/C++).

1. Your program may need to save all of the values for the matrix variable x11 x12 x21 x22 of Qins Algorithm.

2. Your RSA should contain encryption and decryption operations.

3. Your program should demonstrate Small Private Exponent Attack (in Lecture Note 4, aka Wieners attack) on RSA with small decryption exponent (i.e., d < 1 3 ?4 n) given in the lecture: finding d based on n and e.

4. An example of n and e satisfying Wieners condition is:

n=139442204018779381130149348480991172715558421444657111352308 728130213952686953044628842873342966592835045462041550289533043 041524195002763515170262030905603126823321005579498883406744883 474570834008259568413682473391321285456617789464049485470662960 601777636304058647587666143669523166006169933691719739887116010 728803580060491288625430880692286715965725591022383132906827206 667198832963617225264851951369360018690877706367456438852097955 297481300915878836210357330511409810543931737455328285589330560 506586678811986516063395387687021354270151437427054934287148354 68242036488501979845083076916758773475058112957196487

e=3728438759195168737135992109727249348803612435894359189081 738936348226606690336984297449194984522245267347608647851637838 095872369329569971857522894319893342321565064748765439590130905 828618062110655958711360104101926567503619653408915623418784429 679330189884729041367661885435565586952318599099463080887219162 354874117983707707854892379461221207015463083472995141690891986 170606756925711854474324916913314927750891337011838020040295424 415142917065939663073173249929035030071510843219620490640863993 468878684803620906049125234829708750801749587906700784584868164 495039453453030247421811968896558706354352374798351579