-
Notifications
You must be signed in to change notification settings - Fork 176
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
bn_gcd_ext_stein returns different Bezout coefficients #223
Comments
Agreed it's a bug! I never really cared about the bounds and it should be fairly easy to fix. Thanks! :) |
It now hangs: #include <relic_conf.h>
#include <relic.h>
int main(void)
{
if ( core_init() != RLC_OK ) abort();
bn_t A, B, R1, R2, R3;
bn_null(A); bn_new(A);
bn_null(B); bn_new(B);
bn_null(R1); bn_new(R1);
bn_null(R2); bn_new(R2);
bn_null(R3); bn_new(R3);
const char* s1 = "555555555555555550000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000080000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000081624404648562574776480988416386318723821493777533412583444266365419065804535170339197542765321752482359143484437390596115585268050595800018570555555555555555555555555555500000000000000000000000000000000000000000000000000000";
const char* s2 = "66666666666666666666666666660000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001123911187445684340258072669751633781322533717977849594343489334935505860661000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000036363310000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000031696932928800000000000000000000000000000000000000";
bn_read_str(A, s1, strlen(s1), 10);
bn_read_str(B, s2, strlen(s2), 10);
bn_gcd_ext_stein(R1, R2, R3, A, B);
bn_free(A);
bn_free(B);
bn_free(R1);
bn_free(R2);
bn_free(R3);
return 0;
} |
I pushed a not very robust heuristic to fix this later case in 94e5653 to see how it goes. Notice that I also did a minor refactoring of the configuration and now the function is called |
This one still hangs: #include <relic_conf.h>
#include <relic.h>
int main(void)
{
if ( core_init() != RLC_OK ) abort();
bn_t A, B, R1, R2, R3;
bn_null(A); bn_new(A);
bn_null(B); bn_new(B);
bn_null(R1); bn_new(R1);
bn_null(R2); bn_new(R2);
bn_null(R3); bn_new(R3);
const char* s1 = "7000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000008000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000";
const char* s2 = "800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000";
bn_read_str(A, s1, strlen(s1), 10);
bn_read_str(B, s2, strlen(s2), 10);
bn_gcd_ext_binar(R1, R2, R3, A, B);
bn_free(A);
bn_free(B);
bn_free(R1);
bn_free(R2);
bn_free(R3);
return 0;
} |
I just pushed another, more principled, attempt. |
I can't find any more issues. |
This prints:
But if you comment out
bn_gcd_ext
and uncommentbn_gcd_ext_stein
, it prints:Both of these are correct in that they satisfy the equation
X*A + Y*B == GCD(A,B)
.While Bezout coefficients for a given
GCD(A,B)
are not unique, it is my understanding that the particular values returned by the extended GCD algorithm are unique.Specifically, if my reading of Wikipedia is correct, they must satisfy:
The result returned by
bn_gcd_ext_stein
does not satisfy these constraints. Python:Can you confirm this is a bug?
The text was updated successfully, but these errors were encountered: