ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 20 Jun 2024 02:11:43 +0200Generate a random integer with some conditionhttps://ask.sagemath.org/question/77910/generate-a-random-integer-with-some-condition/ I want to generate a random integer of bitsize $n$ with some condition. For example, if we want to generate an integer $e$ of 71 bits satisfying $3e= 1 \bmod 5$, in which the generation is fast to some extent. How to do this in sage.Thu, 20 Jun 2024 00:44:22 +0200https://ask.sagemath.org/question/77910/generate-a-random-integer-with-some-condition/Answer by Max Alekseyev for <p>I want to generate a random integer of bitsize $n$ with some condition. For example, if we want to generate an integer $e$ of 71 bits satisfying $3e= 1 \bmod 5$, in which the generation is fast to some extent. How to do this in sage.</p>
https://ask.sagemath.org/question/77910/generate-a-random-integer-with-some-condition/?answer=77911#post-id-77911$3e\equiv 1\pmod5$ means that $e=5k+2$ for some $k$. Then $e$ having $n=71$ bits means $e\in[2^{n-1},2^n-1]$, which translates into $k\in \big[\lceil (2^{n-1}-2)/5\rceil, \lfloor (2^n-3)/5\rfloor\big]$. Hence, it's enough to generate such a random integer $k$, and then compute $e$ out of it:
n = 71
L = ceil((2^(n-1)-2)/5)
U = (2^n-3)//5
import random
e = random.randint(L,U)*5 + 2
Thu, 20 Jun 2024 01:42:15 +0200https://ask.sagemath.org/question/77910/generate-a-random-integer-with-some-condition/?answer=77911#post-id-77911Comment by Max Alekseyev for <p>$3e\equiv 1\pmod5$ means that $e=5k+2$ for some $k$. Then $e$ having $n=71$ bits means $e\in[2^{n-1},2^n-1]$, which translates into $k\in \big[\lceil (2^{n-1}-2)/5\rceil, \lfloor (2^n-3)/5\rfloor\big]$. Hence, it's enough to generate such a random integer $k$, and then compute $e$ out of it:</p>
<pre><code>n = 71
L = ceil((2^(n-1)-2)/5)
U = (2^n-3)//5
import random
e = random.randint(L,U)*5 + 2
</code></pre>
https://ask.sagemath.org/question/77910/generate-a-random-integer-with-some-condition/?comment=77916#post-id-77916It depends on the type of condition. Any modular condition can be treated similarly to what's done in my answer.Thu, 20 Jun 2024 02:11:43 +0200https://ask.sagemath.org/question/77910/generate-a-random-integer-with-some-condition/?comment=77916#post-id-77916Comment by hamouda for <p>$3e\equiv 1\pmod5$ means that $e=5k+2$ for some $k$. Then $e$ having $n=71$ bits means $e\in[2^{n-1},2^n-1]$, which translates into $k\in \big[\lceil (2^{n-1}-2)/5\rceil, \lfloor (2^n-3)/5\rfloor\big]$. Hence, it's enough to generate such a random integer $k$, and then compute $e$ out of it:</p>
<pre><code>n = 71
L = ceil((2^(n-1)-2)/5)
U = (2^n-3)//5
import random
e = random.randint(L,U)*5 + 2
</code></pre>
https://ask.sagemath.org/question/77910/generate-a-random-integer-with-some-condition/?comment=77915#post-id-77915A general condition according to my choiceThu, 20 Jun 2024 02:08:55 +0200https://ask.sagemath.org/question/77910/generate-a-random-integer-with-some-condition/?comment=77915#post-id-77915Comment by Max Alekseyev for <p>$3e\equiv 1\pmod5$ means that $e=5k+2$ for some $k$. Then $e$ having $n=71$ bits means $e\in[2^{n-1},2^n-1]$, which translates into $k\in \big[\lceil (2^{n-1}-2)/5\rceil, \lfloor (2^n-3)/5\rfloor\big]$. Hence, it's enough to generate such a random integer $k$, and then compute $e$ out of it:</p>
<pre><code>n = 71
L = ceil((2^(n-1)-2)/5)
U = (2^n-3)//5
import random
e = random.randint(L,U)*5 + 2
</code></pre>
https://ask.sagemath.org/question/77910/generate-a-random-integer-with-some-condition/?comment=77913#post-id-77913What specific condition?Thu, 20 Jun 2024 02:06:29 +0200https://ask.sagemath.org/question/77910/generate-a-random-integer-with-some-condition/?comment=77913#post-id-77913Comment by hamouda for <p>$3e\equiv 1\pmod5$ means that $e=5k+2$ for some $k$. Then $e$ having $n=71$ bits means $e\in[2^{n-1},2^n-1]$, which translates into $k\in \big[\lceil (2^{n-1}-2)/5\rceil, \lfloor (2^n-3)/5\rfloor\big]$. Hence, it's enough to generate such a random integer $k$, and then compute $e$ out of it:</p>
<pre><code>n = 71
L = ceil((2^(n-1)-2)/5)
U = (2^n-3)//5
import random
e = random.randint(L,U)*5 + 2
</code></pre>
https://ask.sagemath.org/question/77910/generate-a-random-integer-with-some-condition/?comment=77912#post-id-77912@Max Alekseyev, It is a good idea for this example. If it is possible, is there a general way to generate an integer of bitsize n, with a specific condition. ??Thu, 20 Jun 2024 01:56:58 +0200https://ask.sagemath.org/question/77910/generate-a-random-integer-with-some-condition/?comment=77912#post-id-77912