How to get the seed that will produce a certain result in a Random Number Generator?

Help and Feedback Scripting Support
#1

I really didn’t want to have to make a Devforum post, but after an entire day of having no idea what to do this is practically my last resort.

The title might be slightly confusing, so let me elaborate:

I’m currently working on a Roblox port of the website Library of Babel. It’s basically a website that contains 10^4677 randomly generated books (Practically anything you can write in English, it’s on this website, including this Devforum page Here). It’s able to contain this amount of books as instead of storing them, they can be retrieved by using a Random Number Generator, and using the Hex, Wall, Shelf, and Volume as a seed, then using that to randomly generate 3200 characters for 410 pages.

I already got the main part - randomly generating the book’s title and contents with a Linear Congruential Generator, but I’m missing one of the core features of the Library of Babel- The search feature.

I’m pretty sure the search feature in the Library Of Babel works by getting the seed of the book that would generate that exact line of text and giving you the address of that book.

Problem is, I have NO idea how to do this in Lua (or any other language for that matter), though I know its possible, as the Library Of Babel is a living testimony to this.

The current code I’m using to generate Random Numbers is:

linear_congruential_generator = {}
linear_congruential_generator.__index = linear_congruential_generator

function linear_congruential_generator:random(a, b)
	local y = (self.a * self.x + self.c) % self.m
	self.x = y
	if not a then return y / 0x10000
	elseif not b then
		if a == 0 then return y
		else return 1 + (y % a) end
	else
		return a + (y % (b - a + 1))
	end
end

function lcg(s, r)
	local temp = {}
	setmetatable(temp, linear_congruential_generator)
	temp.a, temp.c, temp.m = 1103515245, 12345, 0x100000000  --from Ansi C
	if r then
		if r == 'nr' then temp.a, temp.c, temp.m = 1664525, 1013904223, 0x100000000 --from Numerical Recipes.
		elseif r == 'mvc' then temp.a, temp.c, temp.m = 214013, 2531011, 0x100000000 end--from MVC
	end
	temp:randomseed(s)
	return temp
end

I’m using randomlua for this, yet I’m only using the LCG, not the MWC or The twister

Is there anyway I could feed a function an array of results, and have it return a seed that would result in those exact results, or is there already an open-sourced random number generator for Lua that can already do something like that?

If you need me to elaborate more, just tell me. It’s a really confusing and specific question, so I understand

1 Like
NextInteger always returning same number, only seen on mobile
#2

Could you use a hashing algorithm?

Something like this for instance:

#3

Can I ask how I could use hashing in this case? I’m totally new to this stuff honestly, nor did I even know what a hashing algorithm WAS until now.

#4

A “hashing algorithm” is a function that can be given a input string or value, and outputs a seemingly random string of numbers. However, it will always spit out the same seemingly random string every time. It can be used to create a system where different objects have different keys associated with them. It is often used in security to protect user information, but I could see you being able to incorporate a very simple one for something like what you’re trying to do.

I was thinking you could possibly convert that array of results to a string, and then use a hashing algorithm to have a assigned value for that set of things.

For whatever string it is given, it will always return the same value.

Tell me if this is something you could see working with your system.

1 Like
#5

It seems like it could work good enough, I’ll try implementing it in a bit and I’ll get back to you if it worked.

2 Likes
#6

Alright, I just tried it and I got this as a result:


It seems like it could work for my use-case, though I have two questions:

  1. Is there a way to reverse the hashing process?
  2. Is there a way to customize the length of the result of the hashing? (Without string.sub because it can’t extend the length)

As you can see, the book’s title’s are really long and the contents are really short.

1 Like
#7
  1. Hashing cannot be reversed, although other types of encoding can. However, you can hash two words and compare the results to tell if hashes are the same.

“book” and “book” will always have the same hash.

  1. I’m not sure of the length/strength of the encoding can be modified with that module, for I have not personally tried it. You would have to look through the function parameters or the docs to see if it if the length is customizable. I would myself but am currently on mobile.
    If this does not end up working out for you, you could try other types of encoding similar to hashing.
1 Like
#8

Wow!
Tricky problem for sure. It looks like the library of babel uses a psuedo-random generator which can be inverted. Looks like the creator of the library designed it himself, so I don’t believe you’ll find lua’s PRG of use unless you can find that invertible (not the same as reversible) quality.
Definitely check out the series on theory behind the library here. I only read up on grains of sand chapter which goes over the algorithmic design and even open sources it. So if you haven’t already, go over this in depth, continue researching beyond that to understand the process and works behind PRGs and why they have seeds.

If you go over hashing implementations, you might find rainbow hashes useful. They’re useful for storage optimization.

Some extra notes on random stuffs from security contexts

  • Hash functions are one way functions, which resemble pseudo-random functions. Although pseudo-random functions themsleves aren’t known to exist. You’ll see Hash-based MAC’s used in integrity and authentication purposes.
  • Psuedo-random generators (PRG) take in some small seed, so they can create a long sequence that is as good as random. These come into play with stream ciphers.
  • Then you also have psuedo-random permutations (PRP) where a distinct input of size n yields a distinct output of size n. Different from a PRF which is indistinguishable from a truly random permutation. Used with block ciphers.

Final note: Best of luck! Hope you’re able to figure it out. Also make the rooms hexagonal, that seems to be an important theme.

2 Likes
#9

Hey!

It’s amazing that someone thought of this before me. This morning I was messing around with the Library of Babel website and I thought of making it a Roblox game. I thought of myself as a genius, and so I started thinking what I needed in order to do so. 5 minutes or so later, I realized I’d need to find a way to get a seed from a randomly generated number, and so I quickly searched “roblox get seed from random number”. I clicked on the first result, and guess what. Someone already thought of the same idea before me.

My question is, did you end up solving this problem? Are you comfortable sharing the method you used?

#10

I actually haven’t got around to finding a good solution for implementing the searching, sadly.
@greatgavin’s post should lead in you the right direction though.

1 Like
#11

All hashes, in theory, should not be reversible. But as our computer get more and more powerful as time goes by, some are already deemed unsafe, like SHA1 and MD5. But if you use something like SHA256 or SHA512 or above, you should be safe. (Unless the hash has previously been brute forced)

To make it safer, you can append a salt to the plaintext before hashing it and store the salt as plaintext somewhere in your db, or even add a pepper to the salted plaintext before hashing them (another random string, but not saved anywhere)

the hashed results’ length is determined by the hashing algorithm used