Skip to main content

Home/ ErgodicPNT/ Group items tagged pseudorandom

Rss Feed Group items tagged

Filter: All | Bookmarks | Topics Simple Middle
arithwsun arithwsun

Szemeredi's theorem - 30 views

http://in-theory.blogspot.com/2006_05_28_archive.html in theory Saturday, June 03, 2006 Szemeredi's theorem Szemeredi's theorem on arithmetic progressions is one of the great triumphs of the "Hung...

szemeredi

started by arithwsun arithwsun on 03 Sep 07 no follow-up yet
arithwsun arithwsun

Unconditional pseudorandom generators for low degree polynomials - 0 views

portal.acm.org/citation.cfm

pseudorandom gowers-norm IT

shared by arithwsun arithwsun on 03 Jan 09 - Cached
  • We give an explicit construction of pseudorandom generators against low degree polynomials over finite fields. We show that the sum of 2d small-biased generators with error ε2O(d) is a pseudorandom generator against degree d polynomials with error ε. This gives a generator with seed length 2O(d) log(n/ε). Our construction follows the recent breakthrough result of Bogadnov and Viola. Their work shows that the sum of d small-biased generators is a pseudo-random generator against degree d polynomials, assuming the Inverse Gowers Conjecture. However, this conjecture is only proven for d=2,3. The main advantage of our work is that it does not rely on any unproven conjectures.
arithwsun arithwsun

Pseudorandom number generation by p-adic ergodic transformations. arXiv Mathematics - C... - 0 views

citeseerx.ist.psu.edu/...F61B8723F2551CBF2AD922A81A9AA6

ergodic p-adic pseudorandom

shared by arithwsun arithwsun on 12 May 08 - Cached
  • Abstract. The paper study counter-dependent pseudorandom number generators based on m-variate (m> 1) ergodic mappings of the space of 2-adic integers Z2. The sequence of internal states of these generators is defined by the recurrence law xi+1 = H B i (xi) mod 2 n, whereas their output sequence is zi = F B i (xi) mod 2 n; here xj, zj are m-dimensional vectors over Z2. It is shown how the results obtained for a univariate case could be extended to a multivariate case. 1.
  • Foundations of Cryptography. Basic Tools. Cambridge Univ – Goldreich - 2001
  • 129 Uniform distribution of sequences – Kuipers, Niederreiter - 1974
  • ...2 more annotations...
  • 22 The art of computer programming. Vol. 2: Seminumerical Algorithms – Knuth - 1981
  • 8 Uniformly distributed sequences of p-adic integers – Anashin - 1994
arithwsun arithwsun

Neal Stephenson on Zeta Function Cryptography - 0 views

www.secamlocal.ex.ac.uk/...zetacrypto.htm

crypt elliptic-curves goldfeld pseudorandom ref

shared by arithwsun arithwsun on 15 Jul 08 - Cached
  • M. Anshel and D. Goldfeld, "Zeta Functions, One-Way Functions, and Pseudorandom Number Generators", Duke Mathematical Journal, Vol. 88 No. 2 (1997) 371-390. "In 1997,Anshel and Goldfeld [6],presented an explicit construction of a pseudorandom number generator arising from an elliptic curve,which can be effectively computed at low computational cost. They introduced a new intractable problem,distinct from integer factorization or the discrete log problem, that leads to a new class of one-way functions based on the theory of zeta functions,and against which there is no known attack."- Richard M. Mollin,"Introduction to Cryptography" CRC Press (2000)
arithwsun arithwsun

Structure and randomness in combinatorics « What's new - 0 views

terrytao.wordpress.com/...nd-randomness-in-combinatorics

combinatorics pseudorandom tao

shared by arithwsun arithwsun on 01 Aug 07 - Cached
  • arithwsun arithwsun on 01 Aug 07
     
    I've just uploaded to the arXiv my lecture notes "Structure and randomness in combinatorics" for my tutorial at the upcoming FOCS 2007 conference in October. This tutorial covers similar ground as my ICM paper (or slides), or my first two Simons lectures, but focuses more on the "nuts-and-bolts" of how structure theorems actually work to separate objects into structured pieces and pseudorandom pieces, for various definitions of "structured" and "pseudorandom".  Given that the target audience consists of computer scientists, I have focused exclusively here on the combinatorial aspects of this dichotomy (applied for instance to functions on the Hamming cube) rather than, say, the ergodic theory aspects (which are covered in Bryna Kra's lecture notes from Montreal, or my notes from Montreal for that matter).  While most of the known applications of these decompositions are number-theoretic (e.g. my theorem with Ben Green), the number theory aspects are not covered in detail in these notes.  (For that, you can read Bernard Host's Bourbaki article, Ben Green's http
arithwsun arithwsun

math.NT/0610050: The primes contain arbitrarily long polynomial progressions - 0 views

arxiv.org/0610050

bergelson-leibman ergodicpnt featured polynomial structure szemeredi transference

shared by arithwsun arithwsun on 31 Jul 07 - Cached
  • arithwsun arithwsun on 31 Jul 07
     
    it is reasonable to conjecture that an analogous result to Theorem 1.3 also holds in higher dimensions.This is however still open even in the linear case, the key difficulty being that the tensor product of pseudorandom measures is not pseudorandom.
arithwsun arithwsun

Milliman Lecture I: Additive combinatorics and the primes « What's new - 0 views

terrytao.wordpress.com/...e-combinatorics-and-the-primes

3-goldbach 4-ap terry

shared by arithwsun arithwsun on 18 May 08 - Cached
  • However, it turns out that if one of the sets, say A, is sufficiently “uniform” or “pseudorandom”, then one can always solve this Goldbach-type problem, regardless of what the other two sets are. This type of fact is often established by Fourier-analytic means (or by closely related techniques, such as spectral theory), but let me give a heuristic combinatorial argument to indicate why one would expect this type of phenomenon to occur.
  • quares Primes Lagrange’s four square theorem: For every positive integer N, there exists a pattern in of the form . Vinogradov’s theorem: For every sufficiently large integer N, there exists a pattern in of the form . Fermat’s two square theorem: For every prime number , there exists a pattern in of the form . Even Goldbach conjecture: For every even number , there exists a pattern in of the form . Fermat’s four square theorem: There does not exist any pattern in of the form with . Green-Tao theorem: For any , there exist infinitely many patterns in of the form with . Pell’s equation: There are infinitely many patterns in of the form . Sophie Germain conjecture: There are infinitely many patterns in of the form .
arithwsun arithwsun

The Möbius and nilsequences conjecture « What's new - 0 views

terrytao.wordpress.com/...us-and-nilsequences-conjecture

featured green-tao mobius-function nilsequences

shared by arithwsun arithwsun on 15 Jul 08 - Cached
  • There is an amusing way to interpret the conjecture (using the close relationship between nilsequences and bracket polynomials) as an assertion of the pseudorandomness of the Liouville function from a computational complexity perspective.   
arithwsun arithwsun

sol18.pdf (application/pdf 对象) - 0 views

www.physics.harvard.edu/...sol18.pdf

poisson-distribution primes pseudorandom

shared by arithwsun arithwsun on 06 Sep 07 - No Cached
arithwsun arithwsun

primes.pdf (application/pdf 对象) - 0 views

www.math.ucla.edu/...primes.pdf

expository primes pseudorandom rsa

shared by arithwsun arithwsun on 18 Aug 07 - No Cached
arithwsun arithwsun

[math/0603450] Pseudo Random test of prime numbers - 0 views

cn.arxiv.org/0603450

ergodicpnt primes pseudorandom

shared by arithwsun arithwsun on 28 Jan 08 - Cached
  • Pseudo Random test of prime numbers Authors: Wang Liang; Huang Yan (Submitted on 18 Mar 2006) Abstract: The prime numbers look like a randomly chosen sequence of natural numbers, but there is still no strict theory to determine 'Randomness'. In these years, cryptography has developed a battery of statistical tests for randomness. In this paper, we just apply these methods to study the distribution of primes. Here the binary sequence constructed by second difference of primes is used as samples. We find this sequence can't reach all the 'random standard' of FIPS 140-1/2, but still show obvious random feature. The interesting self-similarity is also observed in this sequence. These results add the evidence that prime numbers is a chaos system.
arithwsun arithwsun

math.CO/0604456: The ergodic and combinatorial approaches to Szemerédi's theorem - 0 views

front.math.ucdavis.edu/...0604456

combinatorial ergodic ergodicpnt expository pseudorandom structured szemeredi

shared by arithwsun arithwsun on 31 Jul 07 - Cached
  • arithwsun arithwsun on 31 Jul 07
     
    The combinatorial and ergodic approaches may seem rather different at first glance, but we will try to emphasise the many similarities between them.
1 - 13 of 13
Showing 20▼ items per page