Skip to content
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

random big.Integer function #22206

Closed
2 tasks
einar-hjortdal opened this issue Sep 12, 2024 · 3 comments
Closed
2 tasks

random big.Integer function #22206

einar-hjortdal opened this issue Sep 12, 2024 · 3 comments
Labels
Feature Request This issue is made to request a feature.

Comments

@einar-hjortdal
Copy link
Contributor

einar-hjortdal commented Sep 12, 2024

Describe the feature

Generate random big.Integer in the range [0, n)
fn random_integer(n Integer) Integer
Similar to integer_from_bytes, integer_from_i64, integer_from_int, etc.

Use Case

Needed for Secure Remote Password and other crypto implementations.

Proposed Solution

No response

Other Information

No response

Acknowledgements

  • I may be able to implement this feature request
  • This feature might incur a breaking change

Version used

V 0.4.7 79bedff

Environment details (OS name and version, etc.)

V full version: V 0.4.7 ace4e93.79bedff
OS: linux, Linux version 5.14.0-427.33.1.el9_4.x86_64 (mockbuild@pp-el9) (gcc (GCC) 11.4.1 20231218 (Red Hat 11.4.1-3), GNU ld version 2.35.2-43.el9) #1 SMP PREEMPT_DYNAMIC Thu Aug 29 12:00:49 CEST 2024
Processor: 8 cpus, 64bit, little endian, Intel(R) Core(TM) i7-4790K CPU @ 4.00GHz

getwd: /home/einar/Documents/projects/vlang/active/firebird
vexe: /home/einar/.local/lib64/v/v
vexe mtime: 2024-09-12 07:04:54

vroot: OK, value: /home/einar/.local/lib64/v
VMODULES: OK, value: /home/einar/.vmodules
VTMP: OK, value: /tmp/v_1001

Git version: git version 2.43.5
Git vroot status: weekly.2024.35-55-g79bedff1 (5 commit(s) behind V master)
.git/config present: true

CC version: cc (GCC) 11.4.1 20231218 (Red Hat 11.4.1-3)
thirdparty/tcc status: thirdparty-linux-amd64 0134e9b9

Note

You can use the 👍 reaction to increase the issue's priority for developers.

Please note that only the 👍 reaction to the issue itself counts as a vote.
Other reactions and those to comments will not be taken into account.

@einar-hjortdal einar-hjortdal added the Feature Request This issue is made to request a feature. label Sep 12, 2024
@MarcusMWilliams
Copy link

MarcusMWilliams commented Sep 12, 2024 via email

@einar-hjortdal
Copy link
Contributor Author

@hungrybluedev you're the big.Integer man, right? 🙏

@einar-hjortdal
Copy link
Contributor Author

einar-hjortdal commented Sep 13, 2024

Something like this maybe?

// new_random_big_integer creates a random `big.Integer` with range [0, n)
// panics if `n` is 0 or negative.
pub fn new_random_big_integer(n big.Integer) !big.Integer {
	if n.signum < 1 {
		return error('`n` cannot be 0 or negative.')
	}

	max := n - big.integer_from_int(1)
	len := max.bit_len()

	if len == 0 {
		// max must be 0
		return max
	}

	// k is the maximum byte length needed to encode a value < n
	k := (len + 7) / 8

	// b is the number of bits in the most significant byte of n-1
	get_b := fn [len] () u64 {
		b := u64(len % 8)
		if b == 0 {
			return 8
		}
		return b
	}
	b := get_b()

	mut result := big.Integer{}
	for found := false; found == false; {
		mut bytes := rand.read(k)!

		// Clear bits in the first byte to increase the probability that the result is < max
		bytes[0] &= u8(int(1 << b) - 1)

		result = big.integer_from_bytes(bytes)
		if result < max {
			found = true
		}
	}
	return result
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Feature Request This issue is made to request a feature.
Projects
None yet
Development

No branches or pull requests

2 participants