Small solutions to modular arithmetic linear congruenceHow does NaCl Poly1305 implementation do modular multiplication?Understanding elliptic curve encryptionFermats Little Theorem, primitive rootPolynomial ModulusFactoring large $N$ given oracle to find square roots modulo $N$How is it possible that $g^q equiv 1 pmod p$ for a generator g?Given a prime exponent e and a prime number n, find b, where b^e = 1 mod nIncorrect solution for Discrete Log Problem when using the Index Calculus algorithmDiscrete logarithm weak groupSolving the discrete logarithm problem for a weak group
ifconfig shows UP while ip link shows DOWN
What is the limit to a Glyph of Warding's trigger?
Physical only checkdb is failing, but full one is completed successfully
Maximum interval between Alto & Tenor, & intervals when writing for SATB
Could a rotating ring space station have a bolo-like extension?
Alexandrov's generalization of Cauchy's rigidity theorem
How does the Earth's center produce heat?
Is it normal to "extract a paper" from a master thesis?
Align vertices between two edges
Who wrote “A writer only begins a book. A reader finishes it.”
What is Orcus doing with Mind Flayers in the art on the last page of Volo's Guide to Monsters?
Is it safe to redirect stdout and stderr to the same file without file descriptor copies?
Why do testers need root cause analysis?
Knight's Tour on a 7x7 Board starting from D5
Small solutions to modular arithmetic linear congruence
Who were the members of the jury in the Game of Thrones finale?
Toxic, harassing lab environment
How to remove new line added by readarray when using a delimiter?
Flatten not working
What is to the west of Westeros?
Can diplomats be allowed on the flight deck of a commercial European airline?
Is superuser the same as root?
Python script to extract text from PDF with images
Fill area of x^2+y^2>1 and x^2+y^2>4 using patterns and tikzpicture
Small solutions to modular arithmetic linear congruence
How does NaCl Poly1305 implementation do modular multiplication?Understanding elliptic curve encryptionFermats Little Theorem, primitive rootPolynomial ModulusFactoring large $N$ given oracle to find square roots modulo $N$How is it possible that $g^q equiv 1 pmod p$ for a generator g?Given a prime exponent e and a prime number n, find b, where b^e = 1 mod nIncorrect solution for Discrete Log Problem when using the Index Calculus algorithmDiscrete logarithm weak groupSolving the discrete logarithm problem for a weak group
$begingroup$
Let $p$ be a prime number with $N$ bits, let $a,b,c$ be constants. The problem is to find solutions to the equivalent $a x + b y equiv c pmod p$ with both having at most $N/2$ bits.
What algorithmic approaches can solve this problem? Does it have any known hardness reduction?
modular-arithmetic
asked 8 hours ago
rain1rain1
1106
$endgroup$
add a comment |
$begingroup$
Let $p$ be a prime number with $N$ bits, let $a,b,c$ be constants. The problem is to find solutions to the equivalent $a x + b y equiv c pmod p$ with both having at most $N/2$ bits.
What algorithmic approaches can solve this problem? Does it have any known hardness reduction?
modular-arithmetic
asked 8 hours ago
rain1rain1
1106
$endgroup$
1
$begingroup$
Coppersmith's methods are generally used to solve this types of problems. I can't write a proper answer now but have a look at this paper: cits.rub.de/imperia/md/content/may/paper/jochemszmay.pdf
$endgroup$
– Marc Ilunga
7 hours ago
add a comment |
$begingroup$
Let $p$ be a prime number with $N$ bits, let $a,b,c$ be constants. The problem is to find solutions to the equivalent $a x + b y equiv c pmod p$ with both having at most $N/2$ bits.
What algorithmic approaches can solve this problem? Does it have any known hardness reduction?
modular-arithmetic
asked 8 hours ago
rain1rain1
1106
$endgroup$
Let $p$ be a prime number with $N$ bits, let $a,b,c$ be constants. The problem is to find solutions to the equivalent $a x + b y equiv c pmod p$ with both having at most $N/2$ bits.
What algorithmic approaches can solve this problem? Does it have any known hardness reduction?
modular-arithmetic
modular-arithmetic
asked 8 hours ago
rain1rain1
1106
asked 8 hours ago
rain1rain1
1106
asked 8 hours ago
rain1rain1
1106
asked 8 hours ago
rain1rain1
1106
asked 8 hours ago
rain1rain1
1106
1106
1
$begingroup$
Coppersmith's methods are generally used to solve this types of problems. I can't write a proper answer now but have a look at this paper: cits.rub.de/imperia/md/content/may/paper/jochemszmay.pdf
$endgroup$
– Marc Ilunga
7 hours ago
add a comment |
1
$begingroup$
Coppersmith's methods are generally used to solve this types of problems. I can't write a proper answer now but have a look at this paper: cits.rub.de/imperia/md/content/may/paper/jochemszmay.pdf
$endgroup$
– Marc Ilunga
7 hours ago
1
1
$begingroup$
Coppersmith's methods are generally used to solve this types of problems. I can't write a proper answer now but have a look at this paper: cits.rub.de/imperia/md/content/may/paper/jochemszmay.pdf
$endgroup$
– Marc Ilunga
7 hours ago
$begingroup$
Coppersmith's methods are generally used to solve this types of problems. I can't write a proper answer now but have a look at this paper: cits.rub.de/imperia/md/content/may/paper/jochemszmay.pdf
$endgroup$
– Marc Ilunga
7 hours ago
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
You can use lattice reduction to solve this problem.
Pick a large constant $Sinmathbb Z$ and consider the lattice spanned by the rows of the following matrix:
$$
L = beginpmatrix
S a & -1 & 0 & 0 \
S b & 0 & -1 & 0 \
S c & 0 & 0 & S \
S p & 0 & 0 & 0 \
endpmatrix
$$
Now the crucial thing to notice is that some pair $(x,y)inmathbb Z^2$ is a solution to your modular equation if and only if $(0,x,y,S)$ is a vector in this lattice.
Moreover, some vector of the form $vec v=(Sz,x,y,pm S)$ must be part of a short basis, since $beginpmatrixS c & 0 & 0 & Sendpmatrix$ is the only row of $L$ that is non-zero in the last column. Due to the large scaling factor $S$ in the first column, the vector $vec v$ will in fact satisfy $z=0$, and therefore you can find a short solution by computing a reduced basis of $L$.
Here's a sage transcript that demonstrates this:
sage: p = next_prime(2**32)
sage: N = 1+floor(log(p,2)) # bit length
sage: S = 10**N
sage: a, b, c = randrange(p), randrange(p), randrange(p)
sage: a, b, c
(2206104035, 3690588304, 373686466)
sage: L = matrix(ZZ, [[S*a,-1,0,0], [S*b,0,-1,0], [S*c,0,0,S], [S*p,0,0,0]])
sage: L
[22061040350000000000 -1 0 0]
[36905883040000000000 0 -1 0]
[ 3736864660000000000 0 0 10000000000]
[42949673110000000000 0 0 0]
sage: L.LLL()
[ 0 49124 -7835 0]
[ 0 -31049 -82479 0]
[-10000000000 2330 -37438 0]
[ 0 4276 -42601 10000000000]
sage: (4276*a -42601*b) % p == c
True
answered 6 hours ago
yyyyyyyyyyyyyy
9,65933452
$endgroup$
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "281"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f70693%2fsmall-solutions-to-modular-arithmetic-linear-congruence%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
You can use lattice reduction to solve this problem.
Pick a large constant $Sinmathbb Z$ and consider the lattice spanned by the rows of the following matrix:
$$
L = beginpmatrix
S a & -1 & 0 & 0 \
S b & 0 & -1 & 0 \
S c & 0 & 0 & S \
S p & 0 & 0 & 0 \
endpmatrix
$$
Now the crucial thing to notice is that some pair $(x,y)inmathbb Z^2$ is a solution to your modular equation if and only if $(0,x,y,S)$ is a vector in this lattice.
Moreover, some vector of the form $vec v=(Sz,x,y,pm S)$ must be part of a short basis, since $beginpmatrixS c & 0 & 0 & Sendpmatrix$ is the only row of $L$ that is non-zero in the last column. Due to the large scaling factor $S$ in the first column, the vector $vec v$ will in fact satisfy $z=0$, and therefore you can find a short solution by computing a reduced basis of $L$.
Here's a sage transcript that demonstrates this:
sage: p = next_prime(2**32)
sage: N = 1+floor(log(p,2)) # bit length
sage: S = 10**N
sage: a, b, c = randrange(p), randrange(p), randrange(p)
sage: a, b, c
(2206104035, 3690588304, 373686466)
sage: L = matrix(ZZ, [[S*a,-1,0,0], [S*b,0,-1,0], [S*c,0,0,S], [S*p,0,0,0]])
sage: L
[22061040350000000000 -1 0 0]
[36905883040000000000 0 -1 0]
[ 3736864660000000000 0 0 10000000000]
[42949673110000000000 0 0 0]
sage: L.LLL()
[ 0 49124 -7835 0]
[ 0 -31049 -82479 0]
[-10000000000 2330 -37438 0]
[ 0 4276 -42601 10000000000]
sage: (4276*a -42601*b) % p == c
True
answered 6 hours ago
yyyyyyyyyyyyyy
9,65933452
$endgroup$
add a comment |
$begingroup$
You can use lattice reduction to solve this problem.
Pick a large constant $Sinmathbb Z$ and consider the lattice spanned by the rows of the following matrix:
$$
L = beginpmatrix
S a & -1 & 0 & 0 \
S b & 0 & -1 & 0 \
S c & 0 & 0 & S \
S p & 0 & 0 & 0 \
endpmatrix
$$
Now the crucial thing to notice is that some pair $(x,y)inmathbb Z^2$ is a solution to your modular equation if and only if $(0,x,y,S)$ is a vector in this lattice.
Moreover, some vector of the form $vec v=(Sz,x,y,pm S)$ must be part of a short basis, since $beginpmatrixS c & 0 & 0 & Sendpmatrix$ is the only row of $L$ that is non-zero in the last column. Due to the large scaling factor $S$ in the first column, the vector $vec v$ will in fact satisfy $z=0$, and therefore you can find a short solution by computing a reduced basis of $L$.
Here's a sage transcript that demonstrates this:
sage: p = next_prime(2**32)
sage: N = 1+floor(log(p,2)) # bit length
sage: S = 10**N
sage: a, b, c = randrange(p), randrange(p), randrange(p)
sage: a, b, c
(2206104035, 3690588304, 373686466)
sage: L = matrix(ZZ, [[S*a,-1,0,0], [S*b,0,-1,0], [S*c,0,0,S], [S*p,0,0,0]])
sage: L
[22061040350000000000 -1 0 0]
[36905883040000000000 0 -1 0]
[ 3736864660000000000 0 0 10000000000]
[42949673110000000000 0 0 0]
sage: L.LLL()
[ 0 49124 -7835 0]
[ 0 -31049 -82479 0]
[-10000000000 2330 -37438 0]
[ 0 4276 -42601 10000000000]
sage: (4276*a -42601*b) % p == c
True
answered 6 hours ago
yyyyyyyyyyyyyy
9,65933452
$endgroup$
add a comment |
$begingroup$
You can use lattice reduction to solve this problem.
Pick a large constant $Sinmathbb Z$ and consider the lattice spanned by the rows of the following matrix:
$$
L = beginpmatrix
S a & -1 & 0 & 0 \
S b & 0 & -1 & 0 \
S c & 0 & 0 & S \
S p & 0 & 0 & 0 \
endpmatrix
$$
Now the crucial thing to notice is that some pair $(x,y)inmathbb Z^2$ is a solution to your modular equation if and only if $(0,x,y,S)$ is a vector in this lattice.
Moreover, some vector of the form $vec v=(Sz,x,y,pm S)$ must be part of a short basis, since $beginpmatrixS c & 0 & 0 & Sendpmatrix$ is the only row of $L$ that is non-zero in the last column. Due to the large scaling factor $S$ in the first column, the vector $vec v$ will in fact satisfy $z=0$, and therefore you can find a short solution by computing a reduced basis of $L$.
Here's a sage transcript that demonstrates this:
sage: p = next_prime(2**32)
sage: N = 1+floor(log(p,2)) # bit length
sage: S = 10**N
sage: a, b, c = randrange(p), randrange(p), randrange(p)
sage: a, b, c
(2206104035, 3690588304, 373686466)
sage: L = matrix(ZZ, [[S*a,-1,0,0], [S*b,0,-1,0], [S*c,0,0,S], [S*p,0,0,0]])
sage: L
[22061040350000000000 -1 0 0]
[36905883040000000000 0 -1 0]
[ 3736864660000000000 0 0 10000000000]
[42949673110000000000 0 0 0]
sage: L.LLL()
[ 0 49124 -7835 0]
[ 0 -31049 -82479 0]
[-10000000000 2330 -37438 0]
[ 0 4276 -42601 10000000000]
sage: (4276*a -42601*b) % p == c
True
answered 6 hours ago
yyyyyyyyyyyyyy
9,65933452
$endgroup$
You can use lattice reduction to solve this problem.
Pick a large constant $Sinmathbb Z$ and consider the lattice spanned by the rows of the following matrix:
$$
L = beginpmatrix
S a & -1 & 0 & 0 \
S b & 0 & -1 & 0 \
S c & 0 & 0 & S \
S p & 0 & 0 & 0 \
endpmatrix
$$
Now the crucial thing to notice is that some pair $(x,y)inmathbb Z^2$ is a solution to your modular equation if and only if $(0,x,y,S)$ is a vector in this lattice.
Moreover, some vector of the form $vec v=(Sz,x,y,pm S)$ must be part of a short basis, since $beginpmatrixS c & 0 & 0 & Sendpmatrix$ is the only row of $L$ that is non-zero in the last column. Due to the large scaling factor $S$ in the first column, the vector $vec v$ will in fact satisfy $z=0$, and therefore you can find a short solution by computing a reduced basis of $L$.
Here's a sage transcript that demonstrates this:
sage: p = next_prime(2**32)
sage: N = 1+floor(log(p,2)) # bit length
sage: S = 10**N
sage: a, b, c = randrange(p), randrange(p), randrange(p)
sage: a, b, c
(2206104035, 3690588304, 373686466)
sage: L = matrix(ZZ, [[S*a,-1,0,0], [S*b,0,-1,0], [S*c,0,0,S], [S*p,0,0,0]])
sage: L
[22061040350000000000 -1 0 0]
[36905883040000000000 0 -1 0]
[ 3736864660000000000 0 0 10000000000]
[42949673110000000000 0 0 0]
sage: L.LLL()
[ 0 49124 -7835 0]
[ 0 -31049 -82479 0]
[-10000000000 2330 -37438 0]
[ 0 4276 -42601 10000000000]
sage: (4276*a -42601*b) % p == c
True
answered 6 hours ago
yyyyyyyyyyyyyy
9,65933452
answered 6 hours ago
yyyyyyyyyyyyyy
9,65933452
answered 6 hours ago
yyyyyyyyyyyyyy
9,65933452
answered 6 hours ago
yyyyyyyyyyyyyy
9,65933452
9,65933452
add a comment |
add a comment |
Thanks for contributing an answer to Cryptography Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f70693%2fsmall-solutions-to-modular-arithmetic-linear-congruence%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
Coppersmith's methods are generally used to solve this types of problems. I can't write a proper answer now but have a look at this paper: cits.rub.de/imperia/md/content/may/paper/jochemszmay.pdf
$endgroup$
– Marc Ilunga
7 hours ago