diff --git a/policy_manager/chromeos_policy.cc b/policy_manager/chromeos_policy.cc
index 436dc73..eb50887 100644
--- a/policy_manager/chromeos_policy.cc
+++ b/policy_manager/chromeos_policy.cc
@@ -5,6 +5,7 @@
 #include "update_engine/policy_manager/chromeos_policy.h"
 #include "update_engine/policy_manager/policy_utils.h"
 
+#include <algorithm>
 #include <string>
 
 using base::Time;
@@ -87,18 +88,13 @@
 }
 
 TimeDelta ChromeOSPolicy::FuzzedInterval(PRNG* prng, int interval, int fuzz) {
+  DCHECK_GE(interval, 0);
+  DCHECK_GE(fuzz, 0);
   int half_fuzz = fuzz / 2;
-  int lower_bound = interval - half_fuzz;
-  int upper_bound = interval + half_fuzz + 1;
-
   // This guarantees the output interval is non negative.
-  if (lower_bound < 0)
-    lower_bound = 0;
-
-  int fuzzed_interval = lower_bound;
-  if (upper_bound - lower_bound > 0)
-    fuzzed_interval = lower_bound + prng->rand() % (upper_bound - lower_bound);
-  return TimeDelta::FromSeconds(fuzzed_interval);
+  int interval_min = std::max(interval - half_fuzz, 0);
+  int interval_max = interval + half_fuzz;
+  return TimeDelta::FromSeconds(prng->RandMinMax(interval_min, interval_max));
 }
 
 }  // namespace chromeos_policy_manager
diff --git a/policy_manager/prng.h b/policy_manager/prng.h
index 2922e9f..2063bb2 100644
--- a/policy_manager/prng.h
+++ b/policy_manager/prng.h
@@ -5,25 +5,31 @@
 #ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_POLICY_MANAGER_PRNG_H_
 #define CHROMEOS_PLATFORM_UPDATE_ENGINE_POLICY_MANAGER_PRNG_H_
 
-#include <cstdlib>
+#include <random>
 
-#include <base/basictypes.h>
+#include <base/logging.h>
 
 namespace chromeos_policy_manager {
 
-// An unsecure Pseudo-Random Number Generator class based on rand_r(3), which
-// is thread safe and doesn't interfere with other calls to rand().
+// A thread-safe, unsecure, 32-bit pseudo-random number generator based on
+// std::mt19937.
 class PRNG {
  public:
-  // Creates the object using the passed |seed| value as the initial state.
-  explicit PRNG(unsigned int seed) : state_(seed) {}
+  // Initializes the generator with the passed |seed| value.
+  explicit PRNG(uint32_t seed) : gen_(seed) {}
 
-  // Returns a pseudo-random integer in the range [0, RAND_MAX].
-  int rand() { return rand_r(&state_); }
+  // Returns a random unsigned 32-bit integer.
+  uint32_t Rand() { return gen_(); }
+
+  // Returns a random integer uniformly distributed in the range [min, max].
+  int RandMinMax(int min, int max) {
+    DCHECK_LE(min, max);
+    return std::uniform_int_distribution<>(min, max)(gen_);
+  }
 
  private:
-  // The internal state of the PRNG.
-  unsigned int state_;
+  // A pseudo-random number generator.
+  std::mt19937 gen_;
 
   DISALLOW_COPY_AND_ASSIGN(PRNG);
 };
diff --git a/policy_manager/prng_unittest.cc b/policy_manager/prng_unittest.cc
index 4bdf836..cbe7690 100644
--- a/policy_manager/prng_unittest.cc
+++ b/policy_manager/prng_unittest.cc
@@ -17,7 +17,7 @@
   PRNG b(42);
 
   for (int i = 0; i < 1000; ++i) {
-    EXPECT_EQ(a.rand(), b.rand()) << "Iteration i=" << i;
+    EXPECT_EQ(a.Rand(), b.Rand()) << "Iteration i=" << i;
   }
 }
 
@@ -25,12 +25,12 @@
   PRNG a(42);
   PRNG b(5);
 
-  vector<int> values_a;
-  vector<int> values_b;
+  vector<uint32_t> values_a;
+  vector<uint32_t> values_b;
 
   for (int i = 0; i < 100; ++i) {
-    values_a.push_back(a.rand());
-    values_b.push_back(b.rand());
+    values_a.push_back(a.Rand());
+    values_b.push_back(b.Rand());
   }
   EXPECT_NE(values_a, values_b);
 }
@@ -38,10 +38,10 @@
 TEST(PmPRNGTest, IsNotConstant) {
   PRNG prng(5);
 
-  int initial_value = prng.rand();
+  uint32_t initial_value = prng.Rand();
   bool prng_is_constant = true;
   for (int i = 0; i < 100; ++i) {
-    if (prng.rand() != initial_value) {
+    if (prng.Rand() != initial_value) {
       prng_is_constant = false;
       break;
     }
@@ -49,4 +49,19 @@
   EXPECT_FALSE(prng_is_constant) << "After 100 iterations.";
 }
 
+TEST(PmPRNGTest, RandCoversRange) {
+  PRNG a(42);
+  int hits[11] = { 0 };
+
+  for (int i = 0; i < 1000; i++) {
+    int r = a.RandMinMax(0, 10);
+    ASSERT_LE(0, r);
+    ASSERT_GE(10, r);
+    hits[r]++;
+  }
+
+  for (auto& hit : hits)
+    EXPECT_LT(0, hit);
+}
+
 }  // namespace chromeos_policy_manager