Created
December 5, 2025 08:08
-
-
Save MurageKibicho/683fa83e694751b513f872d7cb97d85e to your computer and use it in GitHub Desktop.
2D Gaussian lattice reduction
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| void GaussReduce(fmpz_t x1, fmpz_t y1, fmpz_t x2, fmpz_t y2) | |
| { | |
| //Shortest solution is stored in x1,y1 | |
| fmpz_t mu, dot12, dot11, tmp,tmp2,tmp3; | |
| fmpz_init(mu);fmpz_init(tmp2);fmpz_init(tmp3); fmpz_init(dot12); fmpz_init(dot11); fmpz_init(tmp); | |
| int infiniteLoopCheck = 0; | |
| while(1) | |
| { | |
| //mu = round((v1·v2)/(v1·v1)) | |
| fmpz_mul(dot12, x1, x2);fmpz_mul(tmp, y1, y2);fmpz_add(dot12, dot12, tmp); | |
| fmpz_mul(dot11, x1, x1);fmpz_mul(tmp, y1, y1);fmpz_add(dot11, dot11, tmp); | |
| fmpz_tdiv_q(mu, dot12, dot11); | |
| // v2 = v2 - mu * v1 | |
| fmpz_mul(tmp, mu, x1); fmpz_sub(x2, x2, tmp); | |
| fmpz_mul(tmp, mu, y1); fmpz_sub(y2, y2, tmp); | |
| // ||v2|| < ||v1||, swap | |
| fmpz_mul(tmp, x1, x1); | |
| fmpz_mul(tmp2, y1, y1); fmpz_add(tmp, tmp, tmp2); | |
| fmpz_mul(tmp2, x2, x2); | |
| fmpz_mul(tmp3, y2, y2); fmpz_add(tmp2, tmp2, tmp3); | |
| if(fmpz_cmp(tmp2, tmp) < 0){fmpz_swap(x1, x2);fmpz_swap(y1, y2);} | |
| else{break;} | |
| infiniteLoopCheck += 1; | |
| if(infiniteLoopCheck > INFINITE_LOOP_CHECK_SUM) | |
| { | |
| printf("Gauss reduce may be in infinite loop\n"); | |
| assert(infiniteLoopCheck < INFINITE_LOOP_CHECK_SUM); | |
| } | |
| } | |
| fmpz_clear(mu);fmpz_clear(tmp2);fmpz_clear(tmp3); fmpz_clear(dot12); fmpz_clear(dot11); fmpz_clear(tmp); | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment