In this paper, a new pseudo-random number generator (PRNG) based on improved one- dimensional discrete-space chaotic map is proposed. Like the original, the improved map relies on bijective mapping of permutations and natural numbers. Instead of using standard Lehmer code, we use a mapping computable in linear time, which significantly speeds up the PRNG. Results of NIST 800-22 test suite and TestU01 test suite confirm that the proposed approach can be used for generation of pseudo-random numbers. Due to discrete nature of used chaotic map, the proposed PRNG is not influenced by dynamical degradation and has virtually unlimited key space. Proposed approach has much better ratio between required memory and security level than previous secure one-dimensional discrete-space chaotic PRNGs. Also, proposed PRNG is much faster than other secure PRNGs of the same type. Satisfactory speed and small memory requirements indicate that proposed PRNG has properties desirable for use in devices with limited memory space, such as wireless sensor networks